文章基本信息

标题：On the number of solutions of the equation $Rx^2 + Sy^2 = 1\pmod N$
本地全文：下载
作者：Rana Barua ; Mahabir P. Jhanwar Indian Statistical Institute, Kolkata, India
期刊名称：Sankhya. Series A, mathematical statistics and probability
印刷版ISSN：0976-836X
电子版ISSN：0976-8378
出版年度：2010
卷号：72
期号：01
页码：226--236
出版社：Indian Statistical Institute
摘要：We find by elementary methods the number of solutions of the equation RX2+SY 2 ≡ 1 (mod N), where N is an RSA composite and R, S are given integers coprime to N . When S (or R) is a square modulo N and its square root is known, our approach gives a very simple randomized algorithm for finding a solution. We also find the number of solutions in terms of Legendre and Jacobi symbols.
关键词：Congruences, number of solutions, randomized algorithm, Jacobi and Legendre symbols.