[m-users.] Source Code for Miller-Rabin

[Delmas Buckley]

Matthias,

Attached are source code files primality.m, primes.m, ap.m,
test_primeFactors.m, test_primes.m, and test_prime.m. The file primality.m
with the constants file, ap.m, implement Miller-Rabin. I've tested the
implementation using an Apple PPC machine running Mercury-13.05.1 and also
on a Mac Pro under Ubuntu running Mercury-14.01.1. They pass the tests I
performed.

When running test_primes/2 using two 40-digit numbers with the second
number 5000 larger than the first, I encountered a crash on the PPC
machine: Uncaught Mercury exception: Software error: detected infinite
recursion in func primality.powm/4. When I test pown/4 as a standalone
using large numbers, I'm able to get correct results, so it may be that a
process upstream of powm/4 is a problem. I'm looking into this.

The naming convention for constant valued big integers is ap.n63, for
example, for integer(63). The integer(N) feature doesn't work on the PPC
machine for large values of N. I have been able to use a conversion from
string to big integer to get around that problem. The solution works as
well on x86-64 machines.

Best regards,
Robert Buckley
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurylang.org/archives/users/attachments/20150419/4fe92fa3/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: primality.m
Type: application/octet-stream
Size: 6210 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20150419/4fe92fa3/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: primes.m
Type: application/octet-stream
Size: 6549 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20150419/4fe92fa3/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ap.m
Type: application/octet-stream
Size: 3564 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20150419/4fe92fa3/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test_primeFactors.m
Type: application/octet-stream
Size: 1431 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20150419/4fe92fa3/attachment-0003.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test_primes.m
Type: application/octet-stream
Size: 1414 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20150419/4fe92fa3/attachment-0004.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test_prime.m
Type: application/octet-stream
Size: 1354 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20150419/4fe92fa3/attachment-0005.obj>