Skip to content
gallotyPublic

About

Search for any prime

Resources

Stars

1 star

Watchers

0 watching

Forks

Repository files navigation

annie

Search for any prime number

About

annie is a an OpenCL™ application on GPU.

It performs a fast probable primality test for any number using an Euler test.
a is chosen such that Euler's criterion yields -1: it is the condition of Proth's theorem. If the input is of the form k · 2n + 1, where k is odd and k < 2n, annie performs a primality test.

The input is a Pari/GP math expression. For example: "208003!-1", "3267113#-1", "fibonacci(4740217)", "(sqrtnint(10^999999,1024)+407852)^1024+1".

Philip B. McLaughlin extended Montgomery modular multiplication to modular polynomial arithmetic. This is suited for use with Number Theoretic Transform (NTT) methods for multiplication.
Yves Gallot and George Woltman improved this algorithm by using the polynomials R = 2n - 1 and Q = 2n + 1 and the form x ' = 2-1 R x (mod N).
The proof of the algorithm can be found here.

annie implements an Efficient Modular Exponentiation Proof Scheme. The test is validated with Gerbicz - Li error checking.

Any number with up to approximately 48 million digits can be tested.

Operating system

  • Linux x64
  • Windows x64
  • ARM-based MacOS

Build

Select the makefile of your target. On Windows, MSYS2 distribution and building platform is recommended.
gcc or clang are supported.

Licence

annie is free source code, under the MIT license (see LICENSE). You can redistribute, use and/or modify it. Please give feedback to the authors if improvement is realized. It is distributed in the hope that it will be useful.

TODO

  • Transforms of length 3 · 2n and 5 · 2n.
  • Main and shared memory 128-bit access width.

About

Search for any prime

Resources

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages