- 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 - --- "Adam <a_math_guy@...>" <a_math_guy@...> wrote:
> I assume BLS refers to Brillhart-Lehmer-Selfridge, the version of

"for every prime p" is important. For an actual BLS you only need a set 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.

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

Where did you get your factors from? For most numbers it's exceptionally

> 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.

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

You're trying to prove that there exists an element of order (n-1) in

> 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?

(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

Just use OpenPFGW. Why reinvent the wheel?

> 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.

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/ - 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

There is a bug in Maple's kernel code that causes a severe inefficiency in

> 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.

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. - On Sun, 2 Mar 2003, Phil Carmody wrote:
> > I am using Maple, writing my own code, and just hitting a wall with

Because it is a good way to learn about and play with algorithms without

> > these multi-hundred digit numbers, even for a psp test.

>

> Just use OpenPFGW. Why reinvent the wheel?

getting bogged down in implementation details. Maple is great for this. - On Sun, 2 Mar 2003, Carl Devore wrote:
> I am one of world's leading experts on make Maple code run fast, perhaps

Oh, I forgot to add: I realize that the Maple code will never be as fast

> the leading expert. I would be happy to look at your code and give you

> some pointers.

as compiled code that is specifically designed for primality testing.

But Maple is an excellent system for prototyping and experimenting.