FreeBSD/usr.bin/primes/spsp.c
/* Test for primality using strong pseudoprime tests. */
Test for primality using strong pseudoprime tests.
Test for primality using strong pseudoprime tests .
int
isprime(ubig _n)
{
	uint64_t n = _n;
	if (!spsp(n, 2))
		return (0);
	if (n < 2047ULL)
		return (1);
	if (!spsp(n, 3))
		return (0);
	if (n < 1373653ULL)
		return (1);
	if (!spsp(n, 5))
		return (0);
	if (n < 25326001ULL)
		return (1);
	if (!spsp(n, 7))
		return (0);
	if (n < 3215031751ULL)
		return (1);
	if (!spsp(n, 11))
		return (0);
	if (n < 2152302898747ULL)
		return (1);
	if (!spsp(n, 13))
		return (0);
	if (n < 3474749660383ULL)
		return (1);
	if (!spsp(n, 17))
		return (0);
	if (n < 341550071728321ULL)
		return (1);
	if (!spsp(n, 19))
		return (0);
	if (n < 341550071728321ULL)
		return (1);
	if (!spsp(n, 23))
		return (0);
	if (n < 3825123056546413051)
		return (1);
	assert(n <= SPSPMAX);
	return (0);
}
int isprime ( ubig _n ) { uint64_t n = _n ; if ( ! spsp ( n , 2 ) ) return ( 0 ) ; if ( n < 2047ULL ) return ( 1 ) ; if ( ! spsp ( n , 3 ) ) return ( 0 ) ; if ( n < 1373653ULL ) return ( 1 ) ; if ( ! spsp ( n , 5 ) ) return ( 0 ) ; if ( n < 25326001ULL ) return ( 1 ) ; if ( ! spsp ( n , 7 ) ) return ( 0 ) ; if ( n < 3215031751ULL ) return ( 1 ) ; if ( ! spsp ( n , 11 ) ) return ( 0 ) ; if ( n < 2152302898747ULL ) return ( 1 ) ; if ( ! spsp ( n , 13 ) ) return ( 0 ) ; if ( n < 3474749660383ULL ) return ( 1 ) ; if ( ! spsp ( n , 17 ) ) return ( 0 ) ; if ( n < 341550071728321ULL ) return ( 1 ) ; if ( ! spsp ( n , 19 ) ) return ( 0 ) ; if ( n < 341550071728321ULL ) return ( 1 ) ; if ( ! spsp ( n , 23 ) ) return ( 0 ) ; if ( n < 3825123056546413051 ) return ( 1 ) ; assert ( n <= SPSPMAX ) ; return ( 0 ) ; }
Test for primality using strong pseudoprime tests.
Test for primality using strong pseudoprime tests .
/*
	 * Values from:
	 * C. Pomerance, J.L. Selfridge, and S.S. Wagstaff, Jr.,
	 * The pseudoprimes to 25 * 10^9, Math. Comp. 35(151):1003-1026, 1980.
	 */ /* No SPSPs to base 2 less than 2047. */ /* No SPSPs to bases 2,3 less than 1373653. */ /* No SPSPs to bases 2,3,5 less than 25326001. */ /* No SPSPs to bases 2,3,5,7 less than 3215031751. */ /*
	 * Values from:
	 * G. Jaeschke, On strong pseudoprimes to several bases,
	 * Math. Comp. 61(204):915-926, 1993.
	 */ /* No SPSPs to bases 2,3,5,7,11 less than 2152302898747. */ /* No SPSPs to bases 2,3,5,7,11,13 less than 3474749660383. */ /* No SPSPs to bases 2,3,5,7,11,13,17 less than 341550071728321. */ /* No SPSPs to bases 2,3,5,7,11,13,17,19 less than 341550071728321. */ /*
	 * Value from:
	 * Y. Jiang and Y. Deng, Strong pseudoprimes to the first eight prime
	 * bases, Math. Comp. 83(290):2915-2924, 2014.
	 */ /* No SPSPs to bases 2..23 less than 3825123056546413051. */ /* We can't handle values larger than this. */ /* UNREACHABLE */