- May 10 10:21 AMMay I add a little more explanation to Phil's Pari script for us who are

still novices?

We're trying to find factors of n +/- 1 where n=6*10^1000000000. Phil's

script calculates

n (mod p) for primes p from 2 to 100000 and then squares it. If the

result is 1, then n (mod p)

is either -1 or +1. If it is -1, p is a factor of n+1 and if n(mod p) is

+1, then p is a

factor of n-1. Squaring combined these two tests into one.

Here was Phil's script:

test(p)=centerlift(6*Mod(10,p)^1000000000)^2

forprime(p=2,100000,if(test(p)==1,print(p)))

For Pari novices, like myself, this is a good example of how to use IntMod

types, which

is what you get with the Mod(x,p) function. When you do arithmetic

functions on an IntMod, the

result is always calculated modulo p, so it never gets too big. Now,

10^1000000000 is too big

for Pari to handle, but Mod(10,p)^100000000 does not get too big. Pari

will do this

exponentiation without overflowing anything. Same with the multiply by 6.

An IntMod type is always in the range of 0 to p-1 (mod p), and lift()

converts that type to

an integer in that range. But centerlift( ) converts it to an integer in

the

range (-b/2, b/2], as Phil explained. p-1 is now -1, p-2 would be -2,

etc.

Phil could have made his test use lift() and then compare test(p) to 1 OR

p-1 which would

require a temp variable but eliminate needing to square. Only Phil would

know which

would be faster. Here's how that could be implemented.

test(p)=lift(6*Mod(10,p)^1000000000)

forprime(p=2,100000,temp=test(p);\

if(temp==1,print(p," is a factor of n-1"));\

if(temp==(p-1),print(p," is a factor of n+1")))

I had to put \ at the end of some lines -- I still don't know the rules

about when

they are necessary.

Hope this helps.

Tom Hadley

primenumbers@yahoogroups.com wrote on 05/09/2006 10:01:04 AM:

> Thanks to everyone for the great response - now for the joys of PARI/GP

zeroes,

>

> Regards

>

> Bob

>

> Phil Carmody <thefatphil@...> wrote:

> --- Alan Eliasen <eliasen@...> wrote:

> > Phil Carmody wrote:

> > > --- Bob Gilson <bobgillson@...> wrote:

> > > > A colleague of mine claimed the other day that

> > > > 5, followed by one billion 9's, and 6, followed by 999,999,999

> > with

allegations?

> > > > a further last digit being 1, are in fact twin primes.

> > > > How does anyone go about refuting or confirming such

> > >

to

> > > With Pari/GP in a fraction of a second:

> > > ? test(p)=centerlift(6*Mod(10,p)^1000000000)^2

> > > ? forprime(p=2,100000,if(test(p)==1,print(p)))

> >

> > Impressive timings! This is the only response that actually seemed

> > answer the original question, *how does one go about it* rather than

just

> > enigmatically listing factors, which does not help the original

poster, nor

> > answer the question posed.

numbers

>

> Woo-woo! Brownie-points for Phil!

>

> I was thinking of answering "by evaluating the expressions for the two

> modulo 31", which could have been a middle-ground between my useful :-)

and

> everyone else's useless :-P answers.

those

>

> > Could you explain the mathematics behind this one

> > (especially why you use the centerlift function and what it does) for

> > not familiar with Pari/GP?

b) in

>

> It simply picks a distinguished member of the set of numbers == a (mod

> the range (-b/2, b/2] rather than [0,b). So rather than +1 and p-1

you'll have

> -1 and +1. Hence the square to subsequently turn both of those into 1.

answer

>

> > I would also be interested if the others who posted results would

> > the original question--how one goes about testing claims like this

it's not

> > (efficiently, I hope. I know how to do it several brute-force ways.)

> > Thanks!

>

> Essentially, the same way as the above, I'd bet.

>

> If you've been given a large number that is claimed to be prime, and

> obviously a product of hand-crafted secret numbers, then the best way to

The

> counter the claim of primality is almost always to find a small factor.

> best way to find a small factor is to evaluate the expression for

itmodulo the

> small primes in turn.

[Non-text portions of this message have been removed]

>

> Phil

>

- << Previous post in topic