## programming

Expand Messages
• A QUESTION ABOUT PROGRAMMING This pertains to my post: “An indirect primality test of......” For the sake of this example let x = 1000 i.e. The prime
Message 1 of 2 , Jun 3, 2009

This pertains to my post: �An indirect primality test of......�

For the sake of this example let x = 1000 i.e. The prime suspect is 1000^2
+ 1.

My operation in pari would be

if(Mod(1000^2+1,2)= =1, print(�It is an integer�)

if(Mod(1000^2+1,5)= =2,print(�It is an integer�)

if(Mod(1000^2+1,10)= =3,print(�It is an integer�)

.if(Mod(1000^2+1,17))= = 4,, print(�It is an integer�) and so on.

I can program the above as follows:

{p(k)=if (Mod(1000^2+1,k^2+1)= =k, print(�It is an integer�))}

for(k=1,500,print(p(k)))

Q: Is there a better program?

My knowledge of programming is elementary.

Devaraj

[Non-text portions of this message have been removed]
• ... The idea is to avoid large numbers. If you write Mod( big^something ...) you did not avoid anything. If you write Mod( big, m )^something then you create
Message 2 of 2 , Jun 3, 2009

> My operation in pari would be
> if(Mod(1000^2+1,2)= =1, print("It is an integer")

The idea is to avoid large numbers.
If you write Mod( big^something ...)
you did not avoid anything.
If you write Mod( big, m )^something
then you create "big" as "an element of Z/mZ"
(and thus "smaller than" m)

The exponentiation is not a problem even for large exponents, since it can be done in O(log(exponent)) steps.

When you do the calculation "in Z/mZ", then the number becomes never larger than m, and so the calculation is very fast.

> .if(Mod(1000^2+1,17))= = 4,, print("It is an integer") and so on.

should be

if( Mod(1000,17)^2+1==4, print(integer))

well, actually this works since (I think) a==4 is transformed into
a-4 = 0,
and Mod(x,y)+z is transformed into Mod(x+z,y)

> {p(k)=if (Mod(1000^2+1,k^2+1)= =k, print("It is an integer"))}
> for(k=1,500,print(p(k)))
>
> Q: Is there a better program?

yes:
{p(k)=if (Mod(1000,k^2+1)^2 + 1 == k, print("It is an integer"))}

> My knowledge of programming is elementary.

This is more "conceptual" than "programming", the idea being to work in Z/nZ right from the start, and not to do the reduction mod n
only at the very end, when numbers may have grown huge.

Maximilian
Your message has been successfully submitted and would be delivered to recipients shortly.