Re: mod function and division

From: Phil Carmody (thefatphil_demunged_at_yahoo.co.uk)
Date: 04/05/04 

Date: 05 Apr 2004 15:26:44 +0300

dscheers@wanadoo.nl (David Holland) writes:

> "Gary Shannon" <gary@fiziwig.com> wrote in message news:<74124de1a420dc5f68294b5819caa64a@news.teranews.com>...
> > Take the GCD of the number and another "magic" number which is the product
> > of all the primes < 100.
> >
> > In other words: GCD( N, 2305567963945518424753102147331756070 ) will
> > magically pop out the product of every prime less than 100 that divides N in
> > one step.
> >
> > --gary
> >
>
> To see which if the gcd example above is faster than dividing the
> number by the primes
>
> 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
> 71, 73, 79, 83, 89, 97, Info: In this range a total of 24 numbers
>
> i would advice to count the steps in the above example and compare the
> speed.
> You will find that a plain division of the 24 primes is probably
> faster.

But gcd(N, 3*3*7*11*31*151*331) and gcd(N, 5*5*13*41*61*1321) and various
other expressions like that are faster to compute than your 24 divisions.
Faster than you can calculate even _1_ divison, probably. And that's
both gcds.

Jens Andersen has an implementation of an asymptotically faster
trial-division algorithm that explicitly performs gcds on ever-smaller
products of small primes in heirarchically nested sets.
However, this requires large amounts of RAM for the products of the
small primes, and thus is unsuitable for small devices.

Phil 

-- 
1st bug in MS win2k source code found after 20 minutes: scanline.cpp
2nd and 3rd bug found after 10 more minutes: gethost.c
Both non-exploitable. (The 2nd/3rd ones might be, depending on the CRTL)

Relevant Pages

  • Re: SF: Back to theory
    ... >> all splittings of T^6 can generate an enormous number of gcds to try. ... splittings that gave a dramatic boost to your idea in testing, ... way primes are chosen. ... I view picking gcd candidates at random as independent Bernoulli trials. ...
    (sci.crypt)
  • Re: SF: Back to theory
    ... >> all splittings of T^6 can generate an enormous number of gcds to try. ... splittings that gave a dramatic boost to your idea in testing, ... way primes are chosen. ... I view picking gcd candidates at random as independent Bernoulli trials. ...
    (sci.math)
  • Re: 23 primes in arithmetic progression.
    ... some consider this to be 'cheating', prefering ... an arithmetic progression of primes of length 13, ... 1st bug in MS win2k source code found after 20 minutes: ...
    (sci.math)
  • Re: Cracking DES with C++ is faster than Java?
    ... Bjarne ~ C++ is not a superset of C due to the exceptions. ... all primes are odd" ... 1st bug in MS win2k source code found after 20 minutes: ...
    (comp.lang.cpp)
  • Re: Cracking DES with C++ is faster than Java?
    ... Bjarne ~ C++ is not a superset of C due to the exceptions. ... all primes are odd" ... 1st bug in MS win2k source code found after 20 minutes: ...
    (sci.crypt)
Quantcast