A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem (Q2371449)

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.