Re: Proving primality of an integer

From: Cristiano (cristiano.pi@nsquipo.it)
Date: 02/10/03 

From: "Cristiano" <cristiano.pi@nsquipo.it>
Date: Mon, 10 Feb 2003 21:43:30 GMT

Aldo wrote:
> "Cristiano" <cristiano.pi@nsquipo.it> wrote in message
> news:<XTq1a.208195$AA2.8166443@news2.tin.it>...
>
>>
>> Just a question: if your program say "N is prime", N is really prime
>> without any doubt?
>>
>
> In general only if AKS Conjecture 4 is true.
> So far nobody found an exception.

I'm comparing conjecture 4 against MR test with 3 bases for 128-bit odd
numbers.
I checked about 1,000,000 odd numbers: AKS gave the same answer of MR.

> Your translation of the program into C++ is very good.

Thank you :-)

> I will only add a new simplification to the test routine:
>
> 530 ' Test result
> 540 ' -----------
> 550 block ema(S;*,0)=0
> 560 ema(T;K,0)-=1
> 570 ema(T;0,0)-=N-1
> 580 '
> 590 I=0
> 600 while and{I<R,ema(T;I,0)=0}
> 610 inc I
> 620 wend

So in my implementation we must replace the lines

 S[K]=1; S[0]=N-1;
 I=0; while (I<R && S[I]==T[I]) I++;

with

 T[K]-=1; T[0]-=N-1;
 I=0; while (I<R && T[I]==0) I++;

> There is more I have to say about my program.
> I hope to find some time and post more stuff soon.

Good! I hope so. I'm interested in this stuff.

> Thank you for taking time to read and understand my post.

It's a pleasure :-)

Cristiano