碰撞攻击

这题考验你们的学习能力。我知道你们不会数学，所以教你们如何优雅的暴力

—————————————————————————————————————————————————————————————————

给定一个函数f(x)  其中x为整数。且满足存在某种可逆运算'♢’使得f(a+b)=w(a)♢u(b) 。问在[0,n]中是否存在一个值m。使得f(n)=c。

对于这种比较经典的问题，是存在着暴力的O(sqrt(n))碰撞攻击算法的。这种算法的核心在把f(x)=c  转化为h(y)=g(z) , 这时问题就变成查询 h(y)与g(z)的函数值是否会发生碰撞。

当然，你们可能一脸蒙蔽，不知道怎么构造碰撞。那我现在就给你们演示一下入门教程。

现在以f(x)=k*x %p 为例 。  显然f(a·d+b)=[f(a·d)+f(b)]%p      其中d为常量。

首先 令d=

a的取值范围为0,1,2……d。

b的取值范围为0,1,2……d-1

这时对于任意m属于[0,n]，我们都可以用 ad+b的表达出来。  且a=m/d ,b=m%d 。

现在我们回到问题上来，

求解f(x)=c 转化为了[f(a·d)+f(b)]%p=c   通过移项分离变量后得      f(a·d)=[c-f(b)+p]%p

然后令h(x)=f(d*x)     ,g(x)= [c-f(x)+p]%p. 则原式就是算h(a)与g(b)之间碰撞

因为h(x)，g(x)各自就sqrt(n)种取值。我可以先把h(x)的sqrt(n)种取值算出来，并标记好。

再枚举g(x) 的sqrt(n)种取值， 看这个值是否有被标记，有被标记过则说明发现了碰撞，成功找到了其中的一个解。且这个解为a*d+b

学会了没，这就是学长对你们满满的爱啊,好歹这题给了你们半份题解，教你们做。

——————————————————————————————————————————————————————————————

数据太弱，等待强化

多组数据（数据的组数小于100）

每组输入包含三个整数n,k,c

问是否在[0,n]存在一个数m,使得 k*m%600 000 042=c

0<n<=10⁸

0<k,c<600 000 042

这题其实有log(n)的算法，但是你们八成学不会

若存在解，输出所有解中最小的那个，否则输出-1

57695 209580 274298630
49422 238098 376967504
73493 80586 259473818
73340 202050 518903568
79137 206913 551559740

-1
-1
-1
64929
-1