The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

HDOJ 2466 Cryptography Reloaded (RSA算法)

给出N,e,d,3<=e<31,求出p,q;


二分给BigInteger开方很好用。
另外就是枚举(p-1)*(q-1)在比赛的时候也不失为一种很不错的方法。
import java.math.*;
import java.util.*;
import java.io.*;


public class Main
{
    
public static BigInteger Sqrt(BigInteger x)
    {
        BigInteger l
=new BigInteger("0");
        BigInteger r
=x;
        
while(l.compareTo(r)<0)
        {
            BigInteger mid
=l.add(r).divide(BigInteger.valueOf(2));
            
if(mid.multiply(mid).compareTo(x)<0)
                l
=mid.add(BigInteger.ONE);
            
else if(mid.multiply(mid).compareTo(x)==0)
                
return mid;
            
else

                r
=mid.subtract(BigInteger.ONE);
        }
        
return l;
    }
    
    
public static boolean Judge(BigInteger x)
    {
        BigInteger tem
=new BigInteger("0");
        tem
=Sqrt(x);
        
if(tem.multiply(tem).compareTo(x)==0)
            
return true;
        
else
            
return false;
    }

    
public static void main(String[] args)
    {
        Scanner cin 
= new Scanner (new BufferedInputStream(System.in));
        String sn;
        String se;
        String sd;


        
int ca=0;
        
while(true)
        {
            ca
++;
            sn
=cin.next();
            se
=cin.next();
            sd
=cin.next();

            BigInteger n
=new BigInteger(sn);
            BigInteger e
=new BigInteger(se);
            BigInteger d
=new BigInteger(sd);

            
if(n.compareTo(BigInteger.ZERO)==0 && e.compareTo(BigInteger.ZERO)==0 &&d.compareTo(BigInteger.ZERO)==0)
                
break;

            
for(int i=1;i<=100;i++)
            {
                BigInteger t
=e.multiply(d).subtract(BigInteger.ONE).divide(BigInteger.valueOf(i));
                BigInteger t2
= t.subtract(n).subtract(BigInteger.ONE).pow(2).subtract(BigInteger.valueOf(4).multiply(n));
                
if(Judge( t2 )==true)
                {
                    t2
=Sqrt(t2);
                   
// System.out.println(t2);
                    BigInteger p=n.subtract(t).add(BigInteger.ONE).add(t2).divide(BigInteger.valueOf(2));
                    BigInteger q
=n.subtract(t).add(BigInteger.ONE).subtract(t2).divide(BigInteger.valueOf(2));
                    
if(q.compareTo(p)<0)
                    {
                        BigInteger mm
=q;
                        q
=p;
                        p
=mm;
                    }


                    System.out.println(
"Case #"+ca+":"+" "+p+" "+q);
                    
break;



                }

            }


        }




    }
}


posted on 2010-11-12 17:23 abilitytao 阅读(434) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理