A note on Chang-Lai's modular square algorithm based on the generalized Chinese remainder theorem (Q2371449): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.amc.2006.10.006 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1997269351 / rank | |||
Normal rank |
Revision as of 21:07, 19 March 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