Top
Back: wUnit
Forward: crypto_lib
FastBack: aksaka_lib
FastForward: crypto_lib
Up: atkins_lib
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.12.2.14 Atkin

Procedure from library atkins.lib (see atkins_lib).

Return:
1, if N is prime,
-1, if N is not prime,
0, if the algorithm is not applicable, since there are too few discriminants

Assume:
N is coprime to 6 and different from 1

Note:
K/2 is input for the procedure "disc",
K is input for the procedure "HilbertClassPoly",
B describes the number of recursions being calculated.
The basis of the algorithm is the following theorem:
Let N be an integer coprime to 6 and different from 1 and E be an ellipic curve modulo N.
Assume that we know an integer m and a point P of E(Z/NZ) satisfying the following conditions.
(1) There exists a prime divisor q of m such that q > (4-th root(N)+1)^2.
(2) m*P = O(E) = (0:1:0).
(3) (m/q)*P = (x:y:t) with t element of (Z/NZ)*.
Then N is prime.

Example:
 


Top Back: wUnit Forward: crypto_lib FastBack: aksaka_lib FastForward: crypto_lib Up: atkins_lib Top: Singular Manual Contents: Table of Contents Index: Index About: About this document
            User manual for Singular version 3-1-6, Dec 2012, generated by texi2html.