|
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer (February 23, 1905 – May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s and devised the Lucas–Lehmer test for Mersenne primes. His peripatetic career as a number theorist, with him and his wife taking numerous types of work in the United States and abroad to support themselves during the Great Depression, fortuitously brought him into the center of research into early electronic computing. Early life Lehmer was born in Berkeley, California, to Derrick Norman Lehmer, a professor of mathematics at the University of California, Berkeley, and Clara Eunice Mitchell. He studied physics and earned a Bachelor degree from UC Berkeley, and continued with graduate studies at the University of Chicago. He and his father worked together on Lehmer sieves. Marriage During his studies at Berkeley, Lehmer met Emma Markov ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Berkeley, California
Berkeley ( ) is a city on the eastern shore of San Francisco Bay in northern Alameda County, California, United States. It is named after the 18th-century Irish bishop and philosopher George Berkeley. It borders the cities of Oakland and Emeryville to the south and the city of Albany and the unincorporated community of Kensington to the north. Its eastern border with Contra Costa County generally follows the ridge of the Berkeley Hills. The 2020 census recorded a population of 124,321. Berkeley is home to the oldest campus in the University of California System, the University of California, Berkeley, and the Lawrence Berkeley National Laboratory, which is managed and operated by the university. It also has the Graduate Theological Union, one of the largest religious studies institutions in the world. Berkeley is considered one of the most socially progressive cities in the United States. History Indigenous history The site of today's City of Berkeley was the te ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lehmer's Conjecture
Lehmer's conjecture, also known as the Lehmer's Mahler measure problem, is a problem in number theory raised by Derrick Henry Lehmer. The conjecture asserts that there is an absolute constant \mu>1 such that every polynomial with integer coefficients P(x)\in\mathbb /math> satisfies one of the following properties: * The Mahler measure \mathcal(P(x)) of P(x) is greater than or equal to \mu. * P(x) is an integral multiple of a product of cyclotomic polynomials or the monomial x, in which case \mathcal(P(x))=1. (Equivalently, every complex root of P(x) is a root of unity or zero.) There are a number of definitions of the Mahler measure, one of which is to factor P(x) over \mathbb as :P(x)=a_0 (x-\alpha_1)(x-\alpha_2)\cdots(x-\alpha_D), and then set :\mathcal(P(x)) = , a_0, \prod_^ \max(1,, \alpha_i, ). The smallest known Mahler measure (greater than 1) is for "Lehmer's polynomial" :P(x)= x^+x^9-x^7-x^6-x^5-x^4-x^3+x+1 \,, for which the Mahler measure is the Salem number :\m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lucas–Lehmer Primality Test
In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1876 and subsequently improved by Derrick Henry Lehmer in the 1930s. The test The Lucas–Lehmer test works as follows. Let ''M''''p'' = 2''p'' − 1 be the Mersenne number to test with ''p'' an odd prime. The primality of ''p'' can be efficiently checked with a simple algorithm like trial division since ''p'' is exponentially smaller than ''M''''p''. Define a sequence \ for all ''i'' ≥ 0 by : s_i= \begin 4 & \texti=0; \\ s_^2-2 & \text \end The first few terms of this sequence are 4, 14, 194, 37634, ... . Then ''M''''p'' is prime if and only if :s_ \equiv 0 \pmod. The number ''s''''p'' − 2 mod ''M''''p'' is called the Lucas–Lehmer residue of ''p''. (Some authors equivalently set ''s''1 = 4 and test ''s''''p''−1 mod ''M''''p''). In pseudocode, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Édouard Lucas
__NOTOC__ François Édouard Anatole Lucas (; 4 April 1842 – 3 October 1891) was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him. Biography Lucas was born in Amiens and educated at the École Normale Supérieure. He worked in the Paris Observatory and later became a professor of mathematics at the Lycée Saint Louis and the Lycée Charlemagne in Paris. Lucas served as an artillery officer in the French Army during the Franco-Prussian War of 1870–1871. In 1875, Lucas posed a challenge to prove that the only solution of the Diophantine equation: :\sum_^ n^2 = M^2\; with ''N'' > 1 is when ''N'' = 24 and ''M'' = 70. This is known as the cannonball problem, since it can be visualized as the problem of taking a square arrangement of cannonballs on the ground and building a square pyramid out of them. It was not until 1918 that a proof (using elliptic functions) was found for this ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Number Theory
In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithms for primality testing and integer factorization, finding solutions to diophantine equations, and explicit methods in arithmetic geometry. Computational number theory has applications to cryptography, including RSA, elliptic curve cryptography and post-quantum cryptography, and is used to investigate conjectures and open problems in number theory, including the Riemann hypothesis, the Birch and Swinnerton-Dyer conjecture, the ABC conjecture, the modularity conjecture, the Sato-Tate conjecture, and explicit aspects of the Langlands program. Software packages * Magma computer algebra system * SageMath * Number Theory Library * PARI/GP * Fast Library for Number Theory Further reading * * * * * * * * * * * Referen ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Continued Fraction Factorization
In number theory, the continued fraction factorization method (CFRAC) is an integer factorization algorithm. It is a general-purpose algorithm, meaning that it is suitable for factoring any integer ''n'', not depending on special form or properties. It was described by D. H. Lehmer and R. E. Powers in 1931, and developed as a computer algorithm by Michael A. Morrison and John Brillhart in 1975. The continued fraction method is based on Dixon's factorization method. It uses convergents in the regular continued fraction expansion of :\sqrt,\qquad k\in\mathbb. Since this is a quadratic irrational In mathematics, a quadratic irrational number (also known as a quadratic irrational, a quadratic irrationality or quadratic surd) is an irrational number that is the solution to some quadratic equation with rational coefficients which is irreducibl ..., the continued fraction must be periodic (unless ''n'' is square, in which case the factorization is obvious). It has a time complexity o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lehmer's Totient Problem
In mathematics, Lehmer's totient problem asks whether there is any composite number ''n'' such that Euler's totient function φ(''n'') divides ''n'' − 1. This is an unsolved problem. It is known that φ(''n'') = ''n'' − 1 if and only if ''n'' is prime. So for every prime number ''n'', we have φ(''n'') = ''n'' − 1 and thus in particular φ(''n'') divides ''n'' − 1. D. H. Lehmer conjectured in 1932 that there are no composite numbers with this property. Properties * Lehmer showed that if any composite solution ''n'' exists, it must be odd, square-free, and divisible by at least seven distinct primes (i.e. ''ω(n) ≥ 7''). Such a number must also be a Carmichael number In number theory, a Carmichael number is a composite number n, which in modular arithmetic satisfies the congruence relation: :b^n\equiv b\pmod for all integers b. The relation may also be expressed in the form: :b^\equiv 1\pmod. for all integers .... * In 1980 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lehmer Sequence
In mathematics, a Lehmer sequence is a generalization of a Lucas sequence. Algebraic relations If ''a'' and ''b'' are complex numbers with :a + b = \sqrt :ab = Q under the following conditions: * ''Q'' and ''R'' are relatively prime nonzero integers * a/b is not a root of unity. Then, the corresponding Lehmer numbers are: :U_n(\sqrt,Q) = \frac for ''n'' odd, and :U_n(\sqrt,Q) = \frac for ''n'' even. Their companion numbers are: :V_n(\sqrt,Q) = \frac for ''n'' odd and :V_n(\sqrt,Q) = a^n+b^n for ''n'' even. Recurrence Lehmer numbers form a linear recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ... with :U_n = (R-2Q)U_-Q^2U_ = (a^2+b^2)U_-a^2b^2U_ with initial values U_0=0,\, U_1=1,\, U_2=1,\, U_3=R-Q=a^2+ab+b^2. Similarly the companion sequence s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lehmer Random Number Generator
The Lehmer random number generator (named after D. H. Lehmer), sometimes also referred to as the Park–Miller random number generator (after Stephen K. Park and Keith W. Miller), is a type of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n. The general formula is : X_ = a \cdot X_k \bmod m, where the modulus ''m'' is a prime number or a power of a prime number, the multiplier ''a'' is an element of high multiplicative order modulo ''m'' (e.g., a primitive root modulo ''n''), and the seed ''X'' is coprime to ''m''. Other names are multiplicative linear congruential generator (MLCG) and multiplicative congruential generator (MCG). Parameters in common use In 1988, Park and Miller suggested a Lehmer RNG with particular parameters ''m'' = 2 − 1 = 2,147,483,647 (a Mersenne prime ''M'') and ''a'' = 7 = 16,807 (a primitive root modulo ''M''), now known as MINSTD. Although MINSTD was later criticized by Marsaglia and Sulliv ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pocklington Primality Test
In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer. The test uses a partial factorization of N - 1 to prove that an integer N is prime. It produces a primality certificate to be found with less effort than the Lucas primality test, which requires the full factorization of N - 1. Pocklington criterion The basic version of the test relies on the Pocklington theorem (or Pocklington criterion) which is formulated as follows: Let N > 1 be an integer, and suppose there exist natural numbers and such that Then is prime. Note: Equation () is simply a Fermat primality test. If we find ''any'' value of , not divisible by , such that equation () is false, we may immediately conclude that is not prime. (This divisibility condition is not explicitly stated because it is implied by equation ().) For example, let N = 35. With a = 2, we find that a^ \equiv 9 \pmod. This is enough to prove t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Meissel–Lehmer Algorithm
The Meissel–Lehmer algorithm (after Ernst Meissel and Derrick Henry Lehmer) is an algorithm that computes exact values of the prime-counting function. Description The problem of counting the exact number of primes less than or equal to x, without actually listing them all, dates from Legendre. He observed from the Sieve of Eratosthenes that : \pi (x) - \pi (x^) + 1 = \lfloor x \rfloor - \sum_ \lfloor x/p_i \rfloor + \sum_ \lfloor x/p_ip_j \rfloor - \ldots where \lfloor x \rfloor is the floor function, which denotes the greatest integer less than or equal to x and the p_i run over all primes \leq x^. Since the evaluation of this sum formula is becoming more and more complex and confusing for large x, Meissel tried to simplify the counting of the numbers in the Sieve of Eratosthenes. He and Lehmer introduced therefore certain sieve functions, which are detailed below. Key functions Let p_1, p_2, \ldots, p_n be the first ''n'' primes. For natural number ''a'' ≥ 1, def ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lehmer Mean
In mathematics, the Lehmer mean of a tuple x of positive real numbers, named after Derrick Henry Lehmer, is defined as: :L_p(\mathbf) = \frac. The weighted Lehmer mean with respect to a tuple w of positive weights is defined as: :L_(\mathbf) = \frac. The Lehmer mean is an alternative to power means for interpolating between minimum and maximum via arithmetic mean and harmonic mean. Properties The derivative of p \mapsto L_p(\mathbf) is non-negative : \frac L_p(\mathbf) = \frac , thus this function is monotonic and the inequality :p \le q \Longrightarrow L_p(\mathbf) \le L_q(\mathbf) holds. The derivative of the weighted Lehmer mean is: : \frac = \frac Special cases *\lim_ L_p(\mathbf) is the minimum of the elements of \mathbf. *L_0(\mathbf) is the harmonic mean. *L_\frac\left((x_1, x_2)\right) is the geometric mean of the two values x_1 and x_2. *L_1(\mathbf) is the arithmetic mean. *L_2(\mathbf) is the contraharmonic mean. *\lim_ L_p(\mathbf) is the max ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
