NAME

SYNOPSIS

int asn1_long_is_prime(li, level_of_proof)
asn1_long *li;
int level_of_proof;

int asn1_long_get_prime(li, nbits, level_of_proof)
asn1_long *li;
int nbits, level_of_proof;

int asn1_long_strong_prime(li, nbits, level_of_proof)
asn1_long *li;
int nbits, level_of_proof;

DESCRIPTION

The ASN.1 library routines allow C programmers to describe arbitrary data structures in a machine-independent fashion. All ASN.1 routines require the header "asn1.h" to be included.

These routines deal with manipulation of prime numbers. The long integers are stored using the defined type asn1_long (see asn1_long(9x)) :

• asn1_long_is_prime(\|) determines whether or not the long integer pointed to by li is prime. It returns 1 if the number is prime, 0 otherwise.
• asn1_long_get_prime(\|) returns prime long integer of the specified number of bits nbits.
• asn1_long_strong_prime(\|) returns a prime number li with the desired number of bits "nbits", such that there exists two large prime numbers "R" and "S" that verify :
  1. P - 1 = 0 mod R,
  2. P + 1 = 0 mod S.

The algorithm used here is described in a communication to "Electronics Letters" dated 7th June 1984, Vol 20 No 12, authored by J. Gordon of Cybermation Limited, 39 High Street, Wheathampstead, England.

The primality tests performed by the various routines are stochastic. The number of tests is governed by the "level of proof" parameter. The probability of returning a "false prime" varies as (1/4)**level_of_proof.

If the algorithm ever reports that "P" is nonprime, we can say that "P" definitely isn't prime. But if the algorithm reports 25 times in a row that "P" is "probably prime", we can say that "P" is "almost surely prime". For the probability is less than (1/4)**25 that such a 25-times-in-a-row procedure gives the wrong information about "P". This is less than one chance in a quadrillion.

"SEE ALSO"