Exercise sections are a goldmine of interesting examples, pointers to the literature and potential research projects

polynomial evaluation method of Pollard and Strassen for application to the factorization of Fermat numbers Fn = 22 n + 1. Since we may restrict factor searches to primes of the form p = k 2 n+2 + 1, consider the following approach. Form a product P = ki 2 n+2 + 1 i (all modulo Fn), where the {ki} constitute some set of cleverly chosen integers, with a view to eventual taking of gcd( Fn, P ). The Pollard–Strassen notion of evaluating products of consecutive integers is to be altered: Now

[Assess curve order] Via Algorithm 7.5.6 calculate the integer m that would be # Ea,b(Z n) if n is prime (however if the point-counting algorithm fails, return “n is composite”); // If n is composite, Algorithm 7.5.6 could fail if each candidate for t (mod l) is rejected or if the final curve order is not in the interval √ √ ( n + 1 − 2 n, n + 1 + 2 n). 3. [Attempt to factor] Attempt to factor m = kq where k > 1 and q is a probable prime exceeding 2 n 1 / 4 + 1 , but if this cannot

2 N polynomial in x. But in practice, only some of these 2 N zeros are real (i.e., such that 1 + ix is on the Riemann critical line). For large N , and 2 again experimentally, the rest of the polynomial’s zeros are “expelled” a good distance away from the critical line. The Riemann hypothesis, if it is to be cast in language appropriate to the Hermite expansion, must somehow address this expulsion of nonreal polynomial zeros away from the real axis. Thus the Riemann hypothesis can be cast

c, d < N , with N odd, and R = 2 s > N . 1. [Montgomery mod function M ] M ( c, d) { x = cd; z = y/R; // From Theorem 9.2.1. 2. [Adjust result] if( z ≥ N ) z = z − N ; return z; } The [Adjust result] step in this algorithm always works because cd < RN by hypothesis. The only importance of the choice that R be a power of two is that fast arithmetic may be employed in the evaluation of z = y/R. Algorithm 9.2.6 (Montgomery powering). This algorithm returns xy mod N , for 0 ≤ x < N , y

Alas, the conjecture turns out to be ill-fated. An earlier conjecture that the √ right-hand side could be replaced by 1 x was first disproved in 1963 by 2 Neubauer; later, H. Cohen found a minimal (least x) violation in the form M (7725038629) = 43947 . But the Mertens conjecture (1.26) was finally demolished when it was shown in [Odlyzko and te Riele 1985] that lim sup x− 1 / 2 M ( x) > 1 . 06 , lim inf x− 1 / 2 M ( x) < − 1 . 009 . √ It has been shown by Pintz that for some x less