|
Addition Chain
In mathematics, an addition chain for computing a positive integer can be given by a sequence of natural numbers starting with 1 and ending with , such that each number in the sequence is the sum of two previous numbers. The ''length'' of an addition chain is the number of sums needed to express all its numbers, which is one less than the cardinality of the sequence of numbers. Examples As an example: (1,2,3,6,12,24,30,31) is an addition chain for 31 of length 7, since :2 = 1 + 1 :3 = 2 + 1 :6 = 3 + 3 :12 = 6 + 6 :24 = 12 + 12 :30 = 24 + 6 :31 = 30 + 1 Addition chains can be used for addition-chain exponentiation. This method allows exponentiation with integer exponents to be performed using a number of multiplications equal to the length of an addition chain for the exponent. For instance, the addition chain for 31 leads to a method for computing the 31st power of any number using only seven multiplications, instead of the 30 multiplications that one would get from repeated mult ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science (journal)
''Theoretical Computer Science'' (TCS) is a computer science journal published by Elsevier, started in 1975 and covering theoretical computer science. The journal publishes 52 issues a year. It is abstracted and indexed by Scopus and the Science Citation Index. According to the Journal Citation Reports, its 2020 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a scientometric index calculated by Clarivate that reflects the yearly mean number of citations of articles published in the last two years in a given journal, as ... is 0.827. References Computer science journals Elsevier academic journals Publications established in 1975 {{comp-sci-theory-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bulletin Of The American Mathematical Society
The ''Bulletin of the American Mathematical Society'' is a quarterly mathematical journal published by the American Mathematical Society. Scope It publishes surveys on contemporary research topics, written at a level accessible to non-experts. It also publishes, by invitation only, book reviews and short ''Mathematical Perspectives'' articles. History It began as the ''Bulletin of the New York Mathematical Society'' and underwent a name change when the society became national. The Bulletin's function has changed over the years; its original function was to serve as a research journal for its members. Indexing The Bulletin is indexed in Mathematical Reviews, Science Citation Index, ISI Alerting Services, CompuMath Citation Index, and Current Contents ''Current Contents'' is a rapid alerting service database from Clarivate Analytics, formerly the Institute for Scientific Information and Thomson Reuters. It is published online and in several different printed subject sectio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lucas Chain
In mathematics, a Lucas chain is a restricted type of addition chain, named for the French mathematician Édouard Lucas. It is a sequence :''a''0, ''a''1, ''a''2, ''a''3, ... that satisfies :''a''0=1, and :for each ''k'' > 0: ''a''''k'' = ''a''''i'' + ''a''''j'', and either ''a''''i'' = ''a''''j'' or , ''a''''i'' − ''a''''j'', = ''a''''m'', for some ''i'', ''j'', ''m'' 0, where the Greek letter phi ( .... References * * * {{DEFAULTSORT:Lucas Chain Integer sequences Addition chains ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vectorial Addition Chain
In mathematics, for positive integers ''k'' and ''s'', a vectorial addition chain is a sequence ''V'' of ''k''-dimensional vectors of nonnegative integers ''v''''i'' for −''k'' + 1 ≤ ''i'' ≤ ''s'' together with a sequence ''w'', such that : : ::: ⋮ ::: ⋮ : : ''v''''i'' =''v''''j''+''v''''r'' for all 1≤''i''≤''s'' with -''k''+1≤''j'', ''r''≤''i''-1 : ''v''''s'' = 'n''0,...,''n''''k''-1: ''w'' = (''w''1,...''w''''s''), ''w''''i''=(''j,r''). For example, a vectorial addition chain for 2,18,3is :''V''=( ,0,0 ,1,0 ,0,1 ,1,0 ,2,0 ,4,0 ,4,0 0,8,0 1,9,0 1,9,1 2,18,2 2,18,3 :''w''=((-2,-1),(1,1),(2,2),(-2,3),(4,4),(1,5),(0,6),(7,7),(0,8)) Vectorial addition chains are well suited to perform multi-exponentiation: :Input: Elements ''x''0,...,''x''''k''-1 of an abelian group ''G'' and a vectorial addition chain of dimension ''k'' computing 'n''''0'',...,''n''''k''-1 :Output:The element ''x''0''n''0...''x''''k''-1''n''''r' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Addition-subtraction Chain
An addition-subtraction chain, a generalization of addition chains to include subtraction, is a sequence ''a''0, ''a''1, ''a''2, ''a''3, ... that satisfies :a_0 = 1, \, :\textk > 0,\ a_k = a_i \pm a_j\text0 \leq i,j < k. An addition-subtraction chain for ''n'', of length ''L'', is an addition-subtraction chain such that . That is, one can thereby compute ''n'' by ''L'' additions and/or subtractions. (Note that ''n'' need not be positive. In this case, one may also include ''a''−1 = 0 in the sequence, so that ''n'' = −1 can be obtained by a chain of length 1.) By definition, every addition chain is also an addition-subtraction chain, but not vice versa. Therefore, the length of the ''shortest'' addition-subtraction chain for ''n'' is bounded above by the length of the shortest addition chain for ''n''. In general, however, the determination of a minimal addition-subtraction chain (like the problem of determining a minimum addition chain ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 1995 by Andrew Wiles), have shaped much of mathematical history as new areas of mathematics are developed in order to prove them. Important examples Fermat's Last Theorem In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers a, ''b'', and ''c'' can satisfy the equation ''a^n + b^n = c^n'' for any integer value of ''n'' greater than two. This theorem was first conjectured by Pierre de Fermat in 1637 in the margin of a copy of '' Arithmetica'', where he claimed that he had a proof that was too large to fit in the margin. The first successful proof was released in 1994 by Andrew Wiles, and formally published in 1995, after 358 years of effort by ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Arnold Scholz
Arnold Scholz (24 December 1904 in Berlin – 1 February 1942 in Flensburg) was a German mathematician who proved Scholz's reciprocity law and introduced the Scholz conjecture. Scholz participated in the Second Conference on the Epistemology of the Exact Sciences contributing the paper "On the Use of the Term Holism in Axiomatics" to the discussion on the foundation of mathematics Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathe .... Publications * References * * 1942 deaths 1904 births 20th-century German mathematicians {{Germany-mathematician-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Scholz Conjecture
In mathematics, the Scholz conjecture is a conjecture on the length of certain addition chains. It is sometimes also called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture, after Arnold Scholz who formulated it in 1937 and Alfred Brauer who studied it soon afterward and proved a weaker bound. Statement The conjecture states that :, where is the length of the shortest addition chain producing ''n''. Here, an addition chain is defined as a sequence of numbers, starting with 1, such that every number after the first can be expressed as a sum of two earlier numbers (which are allowed to both be equal). Its length is the number of sums needed to express all its numbers, which is one less than the length of the sequence of numbers (since there is no sum of previous numbers for the first number in the sequence, 1). Computing the length of the shortest addition chain that contains a given number can be done by dynamic programming for small numbers, but it is not known ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hamming Weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string, or the digit sum of the binary representation of a given number and the ''ℓ''₁ norm of a bit vector. In this binary case, it is also called the population count, popcount, sideways sum, or bit summation. History and usage The Hamming weight is named after Richard Hamming although he did not originate the notion. The Hamming weight of binary numbers was already used in 1899 by James W. L. Glaisher to give a formula for the number of odd binomial coefficients in a single row of Pascal's triangle. Irving S. Reed introduced a concept, equivalent to Hamming weight in the binary case, in 1954. Hamming weight is used in several disciplines including information theory, coding ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called the ''length'' of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers (the positions of elements in the sequence) to the elements at each position. The notion of a sequence can be generalized to an indexed family, defined as a function from an ''arbitrary'' index set. For example, (M, A, R, Y) is a sequence of letters with the letter 'M' first and 'Y' last. This sequence differs from (A, R, M, Y). Also, the sequence (1, 1, 2, 3, 5, 8), which contains the number 1 at two different positions, is a valid sequence. Sequences can be ''finite'', as in these examples, or ''infi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prime Factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist. The presumed difficulty of this problem is important for the algorithms used in cryptography such as RSA public-key encryption and the RSA digital signature. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing. In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240-digit (795-bit) number ( RSA-240) utilizing approximately 900 core-years of computing power. The researchers estimated that a 1024-bit R ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
