## Re: [PrimeNumbers] BLS vs psp

Expand Messages
• ... 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 1 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
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 2 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.
• ... 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 3 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.