同時有效地檢查二次剩餘性和雅可比符號
我必須隨機生成一個數字 $ u $ 這樣 $ u \in J(N)-Q(N) $
在哪裡 $ J(N) $ 表示小於的元素集 $ N $ ，其 Jacobi 符號值等於 1；和 $ Q(N) $ 表示二次殘差的集合 $ J(N) $ .
生成它的最佳時間效率方法是什麼？
我想生成這樣的：
1）選擇一個正整數 $ x $ 這樣 $ (x+1)^2 \le {N} $ .
2）選擇任何整數 $ y $ 之間 $ x^2 $ 和 $ (x+1)^2 $ 然後檢查 $ \big{(}\frac{y}{N}\big{)}=1 $ 並繼續，直到我們得到 .
上述方法不正確，下面的評論中提供了反例。
它是好的和正確的嗎？
給定一個複合 $ N $ ，它被要求建構一個隨機 $ u $ 在 $ \mathbb Z_N^* $ 和 $ \big({u\over N}\big)=+1 $ 那不是正方形 $ \pmod N $ .
問題中提出的方法不起作用。反例： $ N=77 $ ; $ x=7 $ ; $ y=53 $ 這是這樣的 $ x^2<y<(x+1)^2\le N $ 和 $ \big({y\over N}\big)=+1 $ . 然而 $ y $ 是二次餘數，因為 $ 53\equiv19^2\pmod {77} $ . 問題是，有人問 $ y $ 不是正方形 $ \pmod N $ ，但問題中提出的構造方法僅確保 $ y $ 不是正方形 $ \mathbb N $ .
這是一種可行的方法，假設我們只知道一個固定的 $ s $ 在 $ \mathbb Z_n^* $ 和 $ \big({s\over N}\big)=+1 $ 那不是正方形 $ \pmod N $ :
- 隨機生成 $ x\in{1\dots N-1} $ ， 直到 $ \gcd(x,N)=1 $ ;
- 計算和輸出 $ u=s\cdot x^2\bmod N $ .
使用Jacobi 符號的乘法性質， $ \big({s\over N}\big)=+1 $ 和 $ \big({x\over N}\big)\ne 0 $ ，它來自於構造 $ u $ 那 $ \big({u\over N}\big)=+1 $ . 而且因為 $ x^2\bmod N $ 是一個非零二次餘數，並且 $ s $ 是一個非零非二次餘數，它們的乘積 $ u\pmod N $ 是一個非零非二次餘數。 $ u $ 是隨機的，因為 $ x $ 是隨機的。我推測（沒有證據） $ u $ 在所需的集合上是均勻的；這可以從證明每個不同的 $ x^2\bmod N $ 和 $ \gcd(x,N)=1 $ 有相等數量的平方根 $ \pmod N $ .
仍有待建設 $ s $ . 在不知道因式分解的情況下，這在一般情況下似乎是不可能的 $ N $ ; 然而，在一些實際情況下， $ N $ 可以生成，因此它的分解是已知但秘密的，這允許有效地生成 $ s $ ; 然後 $ (N,s) $ 可以公開和分解 $ N $ 忘記了。
以下是如何生成 $ (N,s) $ 可以去：
- 生成兩個大的隨機不同素數 $ p $ 和 $ q $ ;
- 計算 $ N=p\cdot q $ ;
- 隨機生成 $ s\in{1\dots N-1} $ 直到 $ \big({s\over p}\big)=-1 $ 和 $ \big({s\over q}\big)=-1 $ ;
- 輸出 $ (N,s) $ .
使用 Jacobi 符號的乘法性質， $ \big({s\over N}\big)=+1 $ . 因為 $ \big({s\over p}\big)=-1 $ 和 $ p $ 是素數， $ s $ 不是二次餘數 $ \pmod p $ ; 因此 $ s $ 不是二次餘數 $ \mod{p\cdot q} $ .
更新以下雨披的回答：如果 $ N=p\cdot q $ 和 $ p $ 和 $ q $ 素數使得 $ p\equiv3\pmod4 $ 和 $ q\equiv3\pmod4 $ ， 然後 $ s=N-1 $ 做這項工作。