A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem (Q2371449)
From MaRDI portal
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