Browse Groups

• 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
View Source
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.

• ... 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
View Source
> 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/
• ... 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
View Source
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
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.
• ... 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
View Source
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.
• ... 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
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.