From owner-svn-src-head@freebsd.org Sun Jun 4 02:36:39 2017 Return-Path: Delivered-To: svn-src-head@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 29550AF89E5; Sun, 4 Jun 2017 02:36:39 +0000 (UTC) (envelope-from cperciva@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 05813141E; Sun, 4 Jun 2017 02:36:38 +0000 (UTC) (envelope-from cperciva@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id v542ach5056563; Sun, 4 Jun 2017 02:36:38 GMT (envelope-from cperciva@FreeBSD.org) Received: (from cperciva@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id v542ac6c056561; Sun, 4 Jun 2017 02:36:38 GMT (envelope-from cperciva@FreeBSD.org) Message-Id: <201706040236.v542ac6c056561@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: cperciva set sender to cperciva@FreeBSD.org using -f From: Colin Percival Date: Sun, 4 Jun 2017 02:36:38 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r319561 - head/usr.bin/primes X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 04 Jun 2017 02:36:39 -0000 Author: cperciva Date: Sun Jun 4 02:36:37 2017 New Revision: 319561 URL: https://svnweb.freebsd.org/changeset/base/319561 Log: Using results from J. Sorenson and J. Webster, Strong pseudoprimes to twelve prime bases, Math. Comp. 86(304):985-1003, 2017. teach primes(6) to enumerate primes up to 2^64 - 1. Until Sorenson and Webster's paper, we did not know how many strong speudoprime tests were required when testing alleged primes between 3825123056546413051 and 2^64 - 1. Reported by: Luiz Henrique de Figueiredo Relnotes: primes(6) now enumerates primes beyond 3825123056546413050, up to a new limit of 2^64 - 1. MFC After: 1 week Modified: head/usr.bin/primes/primes.c head/usr.bin/primes/primes.h head/usr.bin/primes/spsp.c Modified: head/usr.bin/primes/primes.c ============================================================================== --- head/usr.bin/primes/primes.c Sun Jun 4 02:21:38 2017 (r319560) +++ head/usr.bin/primes/primes.c Sun Jun 4 02:36:37 2017 (r319561) @@ -120,7 +120,7 @@ main(int argc, char *argv[]) argv += optind; start = 0; - stop = SPSPMAX; + stop = (uint64_t)(-1); /* * Convert low and high args. Strtoumax(3) sets errno to @@ -147,8 +147,6 @@ main(int argc, char *argv[]) err(1, "%s", argv[1]); if (*p != '\0') errx(1, "%s: illegal numeric format.", argv[1]); - if (stop > SPSPMAX) - errx(1, "%s: stop value too large.", argv[1]); break; case 1: /* Start on the command line. */ Modified: head/usr.bin/primes/primes.h ============================================================================== --- head/usr.bin/primes/primes.h Sun Jun 4 02:21:38 2017 (r319560) +++ head/usr.bin/primes/primes.h Sun Jun 4 02:36:37 2017 (r319561) @@ -72,6 +72,3 @@ extern const size_t pattern_size; /* length of pattern /* Test for primality using strong pseudoprime tests. */ int isprime(ubig); - -/* Maximum value which the SPSP code can handle. */ -#define SPSPMAX 3825123056546413050ULL Modified: head/usr.bin/primes/spsp.c ============================================================================== --- head/usr.bin/primes/spsp.c Sun Jun 4 02:21:38 2017 (r319560) +++ head/usr.bin/primes/spsp.c Sun Jun 4 02:36:37 2017 (r319561) @@ -32,23 +32,32 @@ __FBSDID("$FreeBSD$"); #include "primes.h" -/* Return a * b % n, where 0 <= a, b < 2^63, 0 < n < 2^63. */ +/* Return a * b % n, where 0 < n. */ static uint64_t mulmod(uint64_t a, uint64_t b, uint64_t n) { uint64_t x = 0; + uint64_t an = a % n; while (b != 0) { - if (b & 1) - x = (x + a) % n; - a = (a + a) % n; + if (b & 1) { + x += an; + if ((x < an) || (x >= n)) + x -= n; + } + if (an + an < an) + an = an + an - n; + else if (an + an >= n) + an = an + an - n; + else + an = an + an; b >>= 1; } return (x); } -/* Return a^r % n, where 0 <= a < 2^63, 0 < n < 2^63. */ +/* Return a^r % n, where 0 < n. */ static uint64_t powmod(uint64_t a, uint64_t r, uint64_t n) { @@ -173,9 +182,20 @@ isprime(ubig _n) if (n < 3825123056546413051) return (1); - /* We can't handle values larger than this. */ - assert(n <= SPSPMAX); + /* + * Value from: + * J. Sorenson and J. Webster, Strong pseudoprimes to twelve prime + * bases, Math. Comp. 86(304):985-1003, 2017. + */ - /* UNREACHABLE */ - return (0); + /* No SPSPs to bases 2..37 less than 318665857834031151167461. */ + if (!spsp(n, 29)) + return (0); + if (!spsp(n, 31)) + return (0); + if (!spsp(n, 37)) + return (0); + + /* All 64-bit values are less than 318665857834031151167461. */ + return (1); }