首页 > ACM题库 > HDU-杭电 > hdu 2466 Cryptography Reloaded-数论-[解题报告]java
2014
01-26

hdu 2466 Cryptography Reloaded-数论-[解题报告]java

Cryptography Reloaded

问题描述 :

What do researchers working at ICPC (Institute for Cryptographic Programming and Computing) do for fun? Well, as you probably have expected, in addition to solving algorithm-related problems on online judges, they also like to toy with various cryptographic schemes. Recently one of the researchers, Tom, has become interested in RSA algorithm implementations used in handheld devices.
Note that the description of the general RSA algorithm is as follows:
1) Choose two distinct prime numbers p and q, and let n = pq;
2) Choose an integer e such that gcd(e , (p-1)(q-1)) = 1;
3) Compute the integer d that satisfies the congruence relation
.
de ≡ 1 (mod (p-1)(q-1))
Then, if person A wants to give person B a way to send an encrypted message to him, A can follow the above steps and release (n, e) as his public key. Upon receiving A’s public key, B can simply encrypt message x (0 ≤ x < n) by computing y ≡ xe mod n . This would result in a message which ideally only A could decrypt with his private key d: x ≡ yd mod n .
As the computation power of handheld devices is usually limited, a relatively
small e is usually used to encrypt data. However this can lead to great security risks.
For example, it is quite simple to recover p and q (i.e., factor n) when you have both the public key (n, e) and the private key d. Could you help Tom write a program to demonstrate this?

输入:

There are multiple test cases in the input file.
Each test case contains three integers, n, d, and e (n ≤ 10100 , 3 ≤ e ≤ 31 ). All three integers are given without any preceding zeros. It is guaranteed that all numbers satisfy the condition as given in the problem statement.
Two successive test cases are separated by a blank line. A case with n = 0, d = 0 and e = 0 indicates the end of the input file, and should not be processed by your program.

输出:

There are multiple test cases in the input file.
Each test case contains three integers, n, d, and e (n ≤ 10100 , 3 ≤ e ≤ 31 ). All three integers are given without any preceding zeros. It is guaranteed that all numbers satisfy the condition as given in the problem statement.
Two successive test cases are separated by a blank line. A case with n = 0, d = 0 and e = 0 indicates the end of the input file, and should not be processed by your program.

样例输入:

55 27 3
290203 168101 5
0 0 0

样例输出:

Case #1: 5 11
Case #2: 29 10007

题目:hdu 2466 Cryptography Reloaded

思路:这题就是给出RSA加密的公钥和私钥求初始的两个质数。

开始的时候被几个同余方程给迷惑了,不知从何下手。

然后看了这里的 解题报告 。

然后联立方程组得到:

(p-1)*(q-1)=t   p*q=n

delta=sqrt((t-n-1)^2-4*n)

p=(n+1-t+sqrt(delta))/2;

q=(n+1-t-sqrt(delta))/2;

一直找到满足这样的式子能够整除能够开方的值(竟然不需要判素数)输出就行

import java.math.BigInteger;
import java.util.*;
public class Main{
    public static BigInteger sqrt(BigInteger n)
    {
        BigInteger l=BigInteger.ZERO,r=n,mid,tmp;
        while(l.compareTo(r)<0)
        {
            mid=(l.add(r)).divide(BigInteger.valueOf(2));
            tmp=mid.multiply(mid);
            if(tmp.compareTo(n)>0)
                r=mid.subtract(BigInteger.ONE);
            else if(tmp.compareTo(n)<0)
                l=mid.add(BigInteger.ONE);
            else
                return mid;
        }
        return l;
    }

    public static boolean can_sqrt(BigInteger n) {
        BigInteger tmp=sqrt(n);
        tmp=tmp.multiply(tmp);
        if(tmp.compareTo(n)==0)
            return true;
        return false;
    }

    public static void main(String args[])
    {
        int cas=0;
        Scanner cin=new Scanner(System.in);
        BigInteger n,d,e;
        while(cin.hasNext())
        {
            n=cin.nextBigInteger();
            d=cin.nextBigInteger();
            e=cin.nextBigInteger();
            if(n.compareTo(BigInteger.ZERO)==0 && e.compareTo(BigInteger.ZERO)==0 && d.compareTo(BigInteger.ZERO)==0)
            {
                break;
            }
            d=d.multiply(e);
            d=d.subtract(BigInteger.ONE);
            int i=0;
            while(true)
            {
                i++;
                //  pq  = n
                // de-1 = k*(p-1)*(q-1)      枚举(p-1)(q-1)=tmp
                BigInteger tmp=d.mod(BigInteger.valueOf(i));
                if(tmp.compareTo(BigInteger.ZERO)>0)
                    continue;
                tmp=d.divide(BigInteger.valueOf(i));
                BigInteger delta=((n.subtract(tmp.add(BigInteger.ONE))).pow(2)).subtract(tmp.multiply(BigInteger.valueOf(4)));
                if(can_sqrt(delta)==true)
                {
                    delta=sqrt(delta);
                    BigInteger p,q;
                    p=((n.subtract(tmp.subtract(BigInteger.ONE))).subtract(delta)).divide(BigInteger.valueOf(2));
                    q=((n.subtract(tmp.subtract(BigInteger.ONE))).add(delta)).divide(BigInteger.valueOf(2));
                    if(p.compareTo(q)>0)
                    {
                        BigInteger cnt=p;
                        p=q;
                        q=cnt;
                    }
                    System.out.println("Case #"+ ++cas +": "+p+" "+q);
                    break;

                }

            }
        }
    }
}

解题转自:http://blog.csdn.net/shiyuankongbu/article/details/12522955


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count