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

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

Date: 24 Jul 2004 13:28:31 +0300

beta <beta@s.l> writes:

> 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 you don't expect small a's then this is a bit of a waste,
see next line...

> if(a%2==0 || a%3==0 || a%5==0 || a%7==0 || ... || a%101==0)
> return 0;

Now if you find a residue of 0, check that the original number wasn't
equal to the divisor you just found, and if it was, then you have
a prime

> 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

Given 6733693, it's 100% probably that it will fail.

The above fails on Carmichael numbers:

6733693 = 109 * 163 * 379

(13:08) gp > a=6733693
6733693
(13:08) gp > Mod(2,a)^a
Mod(2, 6733693)
(13:09) gp > Mod(10,a)^a
Mod(10, 6733693)
(13:09) gp > Mod(98765,a)^a
Mod(98765, 6733693)

Also fails on
17098369 113 337 449
17236801 151 211 541
29111881 211 281 491
34657141 191 421 431
37964809 109 379 919
53711113 157 313 1093
56052361 211 421 631
62756641 109 241 2389
64377991 163 487 811
68154001 151 601 751
79411201 193 257 1601
79624621 139 691 829
82929001 281 421 701
84350561 107 743 1061
90698401 103 647 1361
92625121 181 631 811
96895441 109 433 2053
114910489 127 659 1373
115039081 157 313 2341
116682721 281 617 673
... lots more ...
9595140409 103 239 409 953
9624742921 1171 2341 3511
9701285761 433 3457 6481
9764848897 257 769 49409
9789244921 547 2731 6553
9811694593 673 1009 14449
9938059237 619 1237 12979
9973625581 163 1621 37747

What you need is a strong probabe prime test, or SPRP test.
Use Jaeschke's tables for which SPRP tests to use, as found
on http://primepages.org/ (in the 'proving' section).

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)