18021Re: [PrimeNumbers] Checking Large "Prime Numbers"?
- May 9, 2006Thanks to everyone for the great response - now for the joys of PARI/GP
Phil Carmody <thefatphil@...> wrote:
--- Alan Eliasen <eliasen@...> wrote:
> Phil Carmody wrote:Woo-woo! Brownie-points for Phil!
> > --- 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 zeroes,
> > > a further last digit being 1, are in fact twin primes.
> > > How does anyone go about refuting or confirming such allegations?
> > 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 to
> 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.
I was thinking of answering "by evaluating the expressions for the two numbers
modulo 31", which could have been a middle-ground between my useful :-) and
everyone else's useless :-P answers.
> Could you explain the mathematics behind this oneIt simply picks a distinguished member of the set of numbers == a (mod b) in
> (especially why you use the centerlift function and what it does) for those
> not familiar with Pari/GP?
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.
> I would also be interested if the others who posted results would answerEssentially, the same way as the above, I'd bet.
> the original question--how one goes about testing claims like this
> (efficiently, I hope. I know how to do it several brute-force ways.)
If you've been given a large number that is claimed to be prime, and it's not
obviously a product of hand-crafted secret numbers, then the best way to
counter the claim of primality is almost always to find a small factor. The
best way to find a small factor is to evaluate the expression for it modulo the
small primes in turn.
() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed
[stolen with permission from Daniel B. Cristofani]
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
Unsubscribe by an email to: email@example.com
The Prime Pages : http://www.primepages.org/
Mathematics education Mathematics and computer science Number theory
YAHOO! GROUPS LINKS
Visit your group "primenumbers" on the web.
To unsubscribe from this group, send an email to:
Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
[Non-text portions of this message have been removed]
- << Previous post in topic Next post in topic >>