Re: [PrimeNumbers] BLS vs psp
- On Sun, 2 Mar 2003, Adam <a_math_guy@...> wrote:
> You can square and reduce at each step, and extract the bits of n toThere 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
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
- On Sun, 2 Mar 2003, Phil Carmody wrote:
> > I am using Maple, writing my own code, and just hitting a wall withBecause 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, perhapsOh, 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.