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

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

Date: Sat, 24 Jul 2004 17:08:06 GMT

On 24 Jul 2004 13:28:31 +0300, Phil Carmody
<thefatphil_demunged@yahoo.co.uk> wrote:
>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
here a==some_good_number )

>> return 1;
>
>If you don't expect small a's then this is a bit of a waste,
>see next line...

I expect all integers nubers >=0

>> if(a%2==0 || a%3==0 || a%5==0 || a%7==0 || ... || a%101==0)
 here a%101==0 || a%some_good_number==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

I have done it in the above line

>> 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.
I'm not too smart so I have implementated a is_prime() like above but
the result is this
#include "num.h"

int main(void)
{num1 x1="6733693", y1="17098369", x2="17236801", y2="29111881",
x3="34657141", y3="37964809", x4="53711113",
       x5="56052361", y4="9973625581", x6=1, y5=2, x7=3, y6=1, x8=2,
y7=3;

 if(x1.is_prime()) os x1 << " primo\n";
 else os x1 << " non primo\n";

 if(y1.is_prime()) os y1 << " primo\n";
 else os y1 << " non primo\n";

 if(x2.is_prime()) os x2 << " primo\n";
 else os x2 << " non primo\n";
 if(y2.is_prime()) os y2 << " primo\n";
 else os y2 << " non primo\n";

 if(x3.is_prime()) os x3 << " primo\n";
 else os x3 << " non primo\n";
 if(y3.is_prime()) os y3 << " primo\n";
 else os y3 << " non primo\n";

 if(x4.is_prime()) os x4 << " primo\n";
 else os x4 << " non primo\n";
 if(y4.is_prime()) os y4 << " primo\n";
 else os y4 << " non primo\n";
 
 if(x5.is_prime()) os x5 << " primo\n";
 else os x5 << " non primo\n";

 R 0;
}

CC:cont1=6 buffh_len1=2 buffh1=006843B0
CC:cont1=14 buffh_len1=3 buffh1=006885F0
6733693 non primo
17098369 non primo
17236801 non primo
29111881 non primo
34657141 non primo
37964809 non primo
53711113 non primo
9973625581 non primo
56052361 non primo
DD:cont1=0 buffh_len1=3 buffh1=006885F0

is it right?
your 100% is 100% ;)

>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).

PRRRRRRRRRRRRRRRRR to strong prime tests

>Phil