ElGamal数字签名

Time Limit: 1000 mSec

Memory Limit: 32768 KB

Description

在实际生活和工作中,许多事物的处理需要当事人的签名。尤其在现代通信中,签名更是起到了认证、核准、有效和负责等功效。数字签名是现代密码学的一个重要组成部分,自从Diffie和Hellman于1976年首次提出数字签名以来,数字签名就在学术界和计算机网络界得到了迅猛的发展。

著名的公钥算法,椭圆曲线体制,在数字签名中都有一定的应用。ElGamal就是一种原理简单,应用广泛的数字签名方法,它的成功很大程度上取决于求解离散对数问题的困难。

ElGamal的密钥和参数的产生过程如下: 它先选定一个足够大的素数P, 然后在比P小的正数中选取一个随机数g和随机数x, 并且计算出y=gx(mod P) 。然后,{y,g,P}作为公钥,而x则作为保密认证的私钥。

如果你想获取他人的私人信息,那么,你就必须在已知 {y,g,P} 的情况下计算出x(当然,如果要获得明文,还必须攻破或获取签名时使用的Hash函数)。

本题的任务并不复杂,它只需要你对于已知的三元组{y,g,P},设法计算出签名验证的时候用户使用的私钥。

Input

本题有多组输入数据,你必须处理到EOF为止

输入数据有三个整数: P, g, y (2 <= P < 231)

Output

输出仅仅一个数字x ,使得0<x<P并且 y=gx ( mod P) 。如果你认为不存在这样的x那么请输出 ERROR。如果存在多个可能的密钥,请输出最小的一个。

Sample Input

7 5 3
5 1 4

Sample Output

5
ERROR

Hint

Source

福州大学第四届程序设计竞赛

提交代码