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