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

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

Expand Messages
  • Alan Eliasen
    ... with ... Impressive timings! This is the only response that actually seemed to answer the original question, *how does one go about it* rather than just
    Message 1 of 9 , May 8, 2006
    • 0 Attachment
      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. 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?

      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!

      --
      Alan Eliasen
      eliasen@...
      http://futureboy.us/
    • Phil Carmody
      ... 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
      Message 2 of 9 , May 8, 2006
      • 0 Attachment
        --- 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
      • Bob Gilson
        Thanks to everyone for the great response - now for the joys of PARI/GP Regards Bob ... Woo-woo! Brownie-points for Phil! I was thinking of answering by
        Message 3 of 9 , 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]
        • Thomas Hadley
          May 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.
          Message 4 of 9 , May 10, 2006
          • 0 Attachment
            May 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
            >
            > 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
            itmodulo the
            > small primes in turn.
            >
            > Phil
            >


            [Non-text portions of this message have been removed]
          Your message has been successfully submitted and would be delivered to recipients shortly.