Month: September 2008

Number theoretic transform (NTT) is widely recognized as the most efficient method for computing polynomial multiplication with high dimension and integral coefficients, due to its quasilinear complexity.

What is the relationship between the NTT variants that are constructed by splitting the original polynomials into groups of lower-degree sub-polynomials, such as K-NTT, H-NTT, and G3-NTT? Can they be seen as special cases of a certain algorithm under different parameterizations?

To solve the problems, a research team led by Yunlei Zhao published new research on 15 August 2024 in Frontiers of Computer Science.

The team proposed the first Generalized Splitting-Ring Number Theoretic Transform, referred to as GSR-NTT. Then, they investigated the relationship between K-NTT, H-NTT, and G3-NTT.

In the research, they investigate generalized splitting-ring polynomial multiplication based on the monic incremental polynomial variety, and they propose the first Generalized Splitting-Ring Number Theoretic Transform, referred to as GSR-NTT. They demonstrate that K-NTT, H-NTT, and G3-NTT can be regarded as special cases of GSR-NTT under different parameterizations.

They introduce a succinct methodology for complexity analysis, based on which GSR-NTT can derive its optimal parameter settings. They provide GSR-NTT other instantiations based on cyclic convolution-based polynomials and power-of-three cyclotomic polynomials.

They apply GSR-NTT to accelerate polynomial multiplication in the lattice-based scheme named NTTRU and single polynomial multiplication over power-of-three cyclotomic polynomial rings. The experimental results show that, for NTTRU, GSR-NTT achieves speed-ups of 24.7%, 37.6%, and 28.9% for the key generation, encapsulation, and decapsulation algorithms, respectively, leading to a total speed-up of 29.4%.

Future work can focus on implementing GSR-NTT on more platforms.

For more such insights, log into our website https://international-maths-challenge.com

Credit of the article to be given Frontiers Journals

Everyone knows that 2 + 2 = 4, but why do we have arithmetic in the first place, and why is it true? Researchers at the University of Canterbury have recently answered these questions by “reverse engineering” arithmetic from a psychological perspective. To do this, they considered all possible ways that quantities could be combined, and proved (for the first time in mathematical terms) that addition and multiplication are the simplest.

Their proof is based on four assumptions—principles of perceptual organization—that shape how we and other animals experience the world. These assumptions eliminate all possibilities except arithmetic, like how a sculptor’s work reveals a statue hidden in a block of stone.

Monotonicity is the idea of “things changing in the same direction,” and helps us keep track of our place in the world, so that when we approach an object it looms larger but smaller when we move away. Convexity is grounded in intuitions of betweenness. For example, the four corners of a football pitch define the playing field even without boundary lines connecting them. Continuity describes the smoothness with which objects seem to move in space and time. Isomorphism is the idea of sameness or analogy. It’s what allows us to recognize that a cat is more similar to a dog than it is to a rock.

Taken together, these four principles structure our perception of the world so that our everyday experience is ordered and cognitively manageable.

The implications, explained in a paper in Psychological Review, are far-reaching because arithmetic is fundamental for mathematics and science. They suggest arithmetic is biologically-based and a natural consequence of our perception. Mathematics is thus a realization in symbols of the fundamental nature of the mind, and as such both invented and discovered. The seemingly magical success of mathematics in the physical sciences hints that our mind and the world are not separate, but part of a common unity.

For more such insights, log into our website https://international-maths-challenge.com

Credit of the article given to University of Canterbury