A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem (Q2371449): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: A fast modular square computing method based on the generalized Chinese remainder theorem for prime moduli / rank | |||
Normal rank |
Latest revision as of 11:09, 26 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem |
scientific article |
Statements
A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem (English)
0 references
4 July 2007
0 references
The paper deals with an algorithm due to A. Hayashi that computes the square of a number modulo a big prime \(p\). The algorithm is based on the Chinese Remainder Theorem (CRT) and the decomposability of \(p+1\) and \(p+2\). Chang and Lai introduced a generalized CRT that improves Hayashi's procedure. The author of this paper argues that Chang and Lai's improvement is not practical. In fact the papers shows that the generalized CRT is incorrect in most cases and also that the parallel performance claimed is not reasonable.
0 references
modular arithmetic
0 references
modular square algorithm
0 references