Re: Solving the Google "prime number in e" challenge

From: beta (beta_at_s.l)
Date: 07/24/04 

Date: Sat, 24 Jul 2004 05:32:38 GMT

On 22 Jul 2004 09:49:06 -0700, (John Dahlman) wrote:
>3. Lots of ten-digit numbers.
>
>Ten decimal digits holds up to 9,999,999,999 or 10 billion. (American
>billion.) Since over half of those numbers won't fit in a 32-bit integer,
>we switch to the FPU. Fortunately, the FPU can load BCD. (Unfortunately,
>only packed BCD and backwards. Another subroutine to write....)
>
>
>4. Testing for primes: Russian Peasant method -- FAILED
>
>I *thought* I knew how to check each ten-digit number for prime without
>factoring, assuming factoring would be too long. There's a probabilistic
>test for N for prime (if Random ^ (N-1) mod N <> 1, it's not), using the
>"Russian Peasant method" for modular powers. It worked... if the number
>was less than 9 digits long. The ten-digit ones failed on this:
>X * X mod N. An FPU register wouldn't hold the *square* of a ten-digit
>number without rounding.
I'm not an expert but
there is the function ltor(a, b, c)= (a^b)mod c (google for it)
then you can use the result (for some a)
if n is prime and a<p => (a^p) mod p==a
or implement some of prime tests (if you understand them).
Some like this
int is_prime(num a)
{if(a==0||a==1) return 0;
 if(a==2 || a==3 || a==5 || a==7 || ... || a==101 )
                return 1;
 if(a%2==0 || a%3==0 || a%5==0 || a%7==0 || ... || a%101==0)
                return 0;
 if(ltor(2, a, a)!=2 || ltor(10, a, a)!=10 ||
     ltor(some_good_number, a, a)!= some_good_number) return 0;
 return 1;
}
could do the wrong result but seems to me not probable