asn1_long_is_prime asn1_long_get_prime asn1_long_strong_prime - test and generate prime numbers


#include asn1.h

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;


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)) :

This is supposed to make the work of cryptoanalysts harder.

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.


mavcod (9x),
mavros (9x),
mavros-output (9x),
asn1_time (9x),
asn1_malloc (9x),
asn1_long (9x),
asn1_longmath (9x),
asn1_longio (9x),
asn1_longrand (9x)
C. Huitema, "General Presentation of the MAVROS Compiler",INRIA, 1990