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

BLS vs psp

Expand Messages
  • Adam <a_math_guy@yahoo.com>
    I assume BLS refers to Brillhart-Lehmer-Selfridge, the version of which I have runs For every prime p dividing (n-1) there is an integre a with a^(n-1)=1 mod n
    Message 1 of 5 , Mar 2, 2003
    • 0 Attachment
      I assume BLS refers to Brillhart-Lehmer-Selfridge, the version of
      which I have runs

      For every prime p dividing (n-1) there is an integre a with a^(n-1)=1
      mod n and a^[(n-1)/q]<>1 mod n then n is prime.

      Pseudoprime testing runs, given a, if a^(n-1)<>1 mod n then n isn't
      prime.

      Besides the differences in conclusions (proving prime vs proving
      composite), I see these as equally computationally expensive, you
      still need to raise some number a to an extremely large exponent and
      reduce mod n. You can square and reduce at each step, and extract
      the bits of n to determine whether to include that factor of a^(2^k)
      or not, but still, you are performing a heck of a lot of operations
      on a heck of a lot of digits, say, e.g., those Carmicheal numbers
      with prime factors on the order of 1k digits. Am I missing something
      here? Is there a version of BLS where you test an exponent (n-
      1)/q^m, or if (n-1) is factored as product(pi^ei)*N you test only an
      exponent of N?

      I am using Maple, writing my own code, and just hitting a wall with
      these multi-hundred digit numbers, even for a psp test. Broadhurst's
      output came back with something like 33 seconds on it, or maybe .33
      seconds. Even with the factor of 8 that someone posted fast large
      integer multiplication techniques would add, that doesn't account for
      coming back after an hour long class and not having a psp done.

      Adam
    • Phil Carmody
      ... for every prime p is important. For an actual BLS you only need a set of p s such that these known factors is a third of the size of (n-1). ... Where did
      Message 2 of 5 , Mar 2, 2003
      • 0 Attachment
        --- "Adam <a_math_guy@...>" <a_math_guy@...> wrote:
        > I assume BLS refers to Brillhart-Lehmer-Selfridge, the version of
        > which I have runs
        >
        > For every prime p dividing (n-1) there is an integre a with a^(n-1)=1
        > mod n and a^[(n-1)/p]<>1 mod n then n is prime.

        "for every prime p" is important. For an actual BLS you only need a set of
        p's such that these known factors is a third of the size of (n-1).

        > Pseudoprime testing runs, given a, if a^(n-1)<>1 mod n then n isn't
        > prime.
        >
        > Besides the differences in conclusions (proving prime vs proving
        > composite), I see these as equally computationally expensive, you
        > still need to raise some number a to an extremely large exponent and
        > reduce mod n.

        Where did you get your factors from? For most numbers it's exceptionally
        hard to find 1/3 of its size in factors of (n-1). Even if you do have a
        trivial factorisation, you've still got the chance of the a^((n-1)/p) test
        failing, and giving you a 1. Fortunately there are often ways of minimising
        the chance of this failure, but you can't exclude it. As each p could have a
        failure, there's simply more failure potential than for a single PRP test.
        Imagine how much effort it would take to prove q#+1 prime (where '#'is the
        primorial operator). How many a^((n-1)/p) tests do you need to do?

        > You can square and reduce at each step, and extract
        > the bits of n to determine whether to include that factor of a^(2^k)
        > or not, but still, you are performing a heck of a lot of operations
        > on a heck of a lot of digits, say, e.g., those Carmicheal numbers
        > with prime factors on the order of 1k digits. Am I missing something
        > here? Is there a version of BLS where you test an exponent (n-
        > 1)/q^m, or if (n-1) is factored as product(pi^ei)*N you test only an
        > exponent of N?

        You're trying to prove that there exists an element of order (n-1) in
        (Z/nZ)*. The way you do this is by finding an element with order p_i^e_i for
        each p_i where (n-1)=Prod[p_i^e_i]. For this you must find a p-th root of
        unity that is also a p_i^(e_i-1)-th power. If you were to raise a to a power
        (n-1)/p_i^m with m>1, then you'll only prove that p_i^(e_i-(m-1)) divides
        the order of a. This is not enough.

        > I am using Maple, writing my own code, and just hitting a wall with
        > these multi-hundred digit numbers, even for a psp test. Broadhurst's
        > output came back with something like 33 seconds on it, or maybe .33
        > seconds. Even with the factor of 8 that someone posted fast large
        > integer multiplication techniques would add, that doesn't account for
        > coming back after an hour long class and not having a psp done.

        Just use OpenPFGW. Why reinvent the wheel?

        Phil


        =====
        "Only an admission that he does possess weapons of mass destruction
        would do, sources said: 'The rest is just gesture politics." -- Hoon

        "Are you still bombing your wife?" -- Winjer

        __________________________________________________
        Do you Yahoo!?
        Yahoo! Tax Center - forms, calculators, tips, more
        http://taxes.yahoo.com/
      • Carl Devore
        ... There is a bug in Maple s kernel code that causes a severe inefficiency in the modular powering algorithms when the modulus is larger than about 300
        Message 3 of 5 , Mar 2, 2003
        • 0 Attachment
          On Sun, 2 Mar 2003, Adam <a_math_guy@...> wrote:
          > You can square and reduce at each step, and extract the bits of n to
          > determine whether to include that factor of a^(2^k) or not, but
          > still, you are performing a heck of a lot of operations on a heck of a
          > lot of digits, say, e.g., those Carmicheal numbers with prime factors
          > on the order of 1k digits.
          >
          > I am using Maple, writing my own code, and just hitting a wall with
          > these multi-hundred digit numbers, even for a psp test.

          There is a bug in Maple's kernel code that causes a severe inefficiency in
          the modular powering algorithms when the modulus is larger than about 300
          decimal digits. I have documented this and I have written a workaround
          that you can find at http://groups.yahoo.com/group/meg-sugarbush/files.
          Go to directory TimimgTests, and then get file PowerTest.mws. I have
          reported this to Maple, and hopefully it will be fixed in the next
          relaese. You can also look up the article I wrote about this in
          comp.soft-sys.math.maple in the first week of February.

          Also, Maple uses Karatsuba for large-integer multiplication and not an
          FFT-based method. This is probably not a drawback for numbers in the
          hundreds of digits, but it may be for numbers in the thousands of digits.
          Perhaps this will change in a future release. In the top-level directory
          at http://groups.yahoo.com/group/meg-sugarbush/files,you can get the file
          PrimRoot.mws where I do some work with numbers about 20,000 digits,
          specifically, verifying that 2^32-1 is a primitive root of the prime
          1030770*(2^32-1)^(2^11)+1.

          I am one of world's leading experts on make Maple code run fast, perhaps
          the leading expert. I would be happy to look at your code and give you
          some pointers.
        • Carl Devore
          ... Because it is a good way to learn about and play with algorithms without getting bogged down in implementation details. Maple is great for this.
          Message 4 of 5 , Mar 2, 2003
          • 0 Attachment
            On Sun, 2 Mar 2003, Phil Carmody wrote:
            > > I am using Maple, writing my own code, and just hitting a wall with
            > > these multi-hundred digit numbers, even for a psp test.
            >
            > Just use OpenPFGW. Why reinvent the wheel?

            Because it is a good way to learn about and play with algorithms without
            getting bogged down in implementation details. Maple is great for this.
          • Carl Devore
            ... Oh, I forgot to add: I realize that the Maple code will never be as fast as compiled code that is specifically designed for primality testing. But Maple
            Message 5 of 5 , Mar 2, 2003
            • 0 Attachment
              On Sun, 2 Mar 2003, Carl Devore wrote:
              > I am one of world's leading experts on make Maple code run fast, perhaps
              > the leading expert. I would be happy to look at your code and give you
              > some pointers.

              Oh, I forgot to add: I realize that the Maple code will never be as fast
              as compiled code that is specifically designed for primality testing.
              But Maple is an excellent system for prototyping and experimenting.
            Your message has been successfully submitted and would be delivered to recipients shortly.