Good Bye 2018 : G. New Year and the Factorisation Collaboration

ここらへんの知識足りないな…。
https://codeforces.com/contest/1091/problem/G

問題

2^1024以下の整数Nが与えられる。
これは2～10個の(4n+3)の形で表現できる素数の積である。
この整数Nを素因数分解せよ。

なお、この問題では以下の計算結果を問い合わせることができる。

• 2値x,yに対し、(x+y)%N,(x-y)%N,(x*y)%N,(x/y)%N, pow(x,y)%N
• xに対しsqrt(x)%N

解法

多倍長整数が使える環境では、前者は自分で計算できるので使う必要はない。
問題は後者。

今回の問題設定のようなNに対し、平方根は２通り考えられる。
x*x=y*y=zとする。
乱数xに対しsqrt(x*x)を問い合わせると、1/2の確率でxではなくyが返ってくることになる。
この時、x*x=y*y (mod N)より(x+y)(x-y)=0 (mod N)なので、(x+y)(x-y)はNの約数である。
この情報を用いてNを分解していけばよい。

import math
import random

N=int(input())

S=set()
S.add(N)
for i in range(40):
	x = random.randint(1,N-1)
	print("sqrt %d" % (x*x%N))
	y = int(input())
	
	a = (x+y)%N
	
	T=set()
	for s in S:
		T.add(math.gcd(s,a))
		T.add(s//math.gcd(s,a))
	S=T

S-={1}
S=list(S)
print("! %d %s" % (len(S), " ".join([str(x) for x in S])))

まとめ

4n+3と平方根でピンとくる人には来るようで。
うーむ、知識不足。