Loading ...
Sorry, an error occurred while loading the content.

18021Re: [PrimeNumbers] Checking Large "Prime Numbers"?

Expand Messages
  • Bob Gilson
    May 9, 2006
    • 0 Attachment
      Thanks to everyone for the great response - now for the joys of PARI/GP

      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 zeroes,
      > with
      > > > 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.

      Woo-woo! Brownie-points for Phil!

      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 one
      > (especially why you use the centerlift function and what it does) for those
      > not familiar with Pari/GP?

      It simply picks a distinguished member of the set of numbers == a (mod b) in
      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 answer
      > the original question--how one goes about testing claims like this
      > (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 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.

      Phil

      () 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
      http://mail.yahoo.com


      Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      The Prime Pages : http://www.primepages.org/





      SPONSORED LINKS
      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:
      primenumbers-unsubscribe@yahoogroups.com

      Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.


      ---------------------------------





      [Non-text portions of this message have been removed]
    • Show all 9 messages in this topic