binary quadratic sieve

SearchAdvancedHelp

(0.002 seconds)

1—10 of 41 matching pages

1: 27.18 Methods of Computation: Primes

… ►An analytic approach using a contour integral of the Riemann zeta function (§25.2(i)) is discussed in Borwein et al. (2000). ►The Sieve of Eratosthenes (Crandall and Pomerance (2005, §3.2)) generates a list of all primes below a given bound. An alternative procedure is the binary quadratic sieve of Atkin and Bernstein (Crandall and Pomerance (2005, p. 170)). …

2: 27.19 Methods of Computation: Factorization

… ►These algorithms include the Continued Fraction Algorithm (cfrac), the Multiple Polynomial Quadratic Sieve (mpqs), the General Number Field Sieve (gnfs), and the Special Number Field Sieve (snfs). …

3: 27.22 Software

… ►

Mathematica. PrimeQ combines strong pseudoprime tests for the bases 2 and 3 and a Lucas pseudoprime test. No known composite numbers pass these three tests, and Bleichenbacher (1996) has shown that this combination of tests proves primality for integers below ${10}^{16}$. Provable PrimeQ uses the Atkin–Goldwasser–Kilian–Morain Elliptic Curve Method to prove primality. FactorInteger tries Brent–Pollard rho, Pollard $p-1$, and then cfrac after trial division. See §27.19. ecm is available also, and the Multiple Polynomial Quadratic sieve is expected in a future release.

For additional Mathematica routines for factorization and primality testing, including several different pseudoprime tests, see Bressoud and Wagon (2000).

…

4: 3.1 Arithmetics and Error Measures

… ►

§3.1(i) Floating-Point Arithmetic

►Computer arithmetic is described for the binary based system with base 2; another system that has been used is the hexadecimal system with base 16. ►A nonzero normalized binary floating-point machine number $x$ is represented as … ►In the case of the normalized binary interchange formats, the representation of data for binary32 (previously single precision) ($N=32$, $p=24$, $E_{\min }=-126$, $E_{\max }=127$), binary64 (previously double precision) ($N=64$, $p=53$, $E_{\min }=-1022$, $E_{\max }=1023$) and binary128 (previously quad precision) ($N=128$, $p=113$, $E_{\min }=-16382$, $E_{\max }=16383$) are as in Figure 3.1.1. … ►

Figure 3.1.1: Floating-point arithmetic. Representation of data in the binary interchange formats for binary32, binary64 and binary128 (previously single, double and quad precision).

…

5: 27.9 Quadratic Characters

§27.9 Quadratic Characters

►For an odd prime $p$, the Legendre symbol $(n|p)$ is defined as follows. …If $p$ does not divide $n$, then $(n|p)$ has the value $1$ when the quadratic congruence $x^2\equiv n(modp)$ has a solution, and the value $-1$ when this congruence has no solution. … ►If $p,q$ are distinct odd primes, then the quadratic reciprocity law states that … ►If an odd integer $P$ has prime factorization $P={\prod }_{r=1}^{\nu \left(n\right)}{p}_r^{a_r}$, then the Jacobi symbol $(n|P)$ is defined by $(n|P)={\prod }_{r=1}^{\nu \left(n\right)}{(n|p_r)}^{a_r}$, with $(n|1)=1$. …

6: 24.14 Sums

… ►

§24.14(i) Quadratic Recurrence Relations

… ►

§24.14(ii) Higher-Order Recurrence Relations

…

7: 3.8 Nonlinear Equations

… ►If $p=2$, then the convergence is quadratic; if $p=3$, then the convergence is cubic, and so on. … ►If $\zeta$ is a simple zero, then the iteration converges locally and quadratically. … ►It converges locally and quadratically for both $ℝ$ and $ℂ$. … ►The method converges locally and quadratically, except when the wanted quadratic factor is a multiple factor of $q(z)$. … ►The quadratic nature of the convergence is evident. …

8: 15.17 Mathematical Applications

… ►The logarithmic derivatives of some hypergeometric functions for which quadratic transformations exist (§15.8(iii)) are solutions of Painlevé equations. … ►Quadratic transformations give insight into the relation of elliptic integrals to the arithmetic-geometric mean (§19.22(ii)). …

9: 13.12 Products

… ►For generalizations of this quadratic relation see Majima et al. (2000). …

10: 16.6 Transformations of Variable

… ►

Quadratic

…