My Weblog

Blog about programming and math

SPOJ 4186. Break a New RSA system

SPOJ 4186. Break a New RSA system is related to searching a root in given interval. We have
n = p * q * r \hspace{ 20 pt} (1)
\phi_{n} = ( p - 1 ) * ( q - 1 ) * ( r - 1 ) \hspace{ 20 pt} (2)
\sigma_{ n }= ( p + 1 ) * ( q + 1 ) * ( r + 1 )  \hspace{ 20 pt} (3)
Adding 2 and 3
\frac {\phi_{n} + \sigma_{n}} {2} = p + q + r + n  \hspace{ 20 pt} (4)
Subtracting 2 and 3
\frac {\sigma_{n} - \phi_{n}  } {2} = qr + pr + pq + 1  \hspace{ 20 pt} (5)
In 5 , we can replace qr by \frac {n} {p} and take p common from second and third so our final equation will be
\frac {\sigma_{n} - \phi_{n}  } {2} = \frac {n} {p} + p(r + q ) + 1  \hspace{ 20 pt} (6)
From equation 4 , replacing the valuve r + q in 6 we get a cubic equation in p . Our final equation will be
2*p^3 + (2 * n - \phi_{n} - \sigma_{n})*p^2 + (  \sigma_{n} - \phi_{n} - 2 ) * p + (-2n) = 0 \hspace{ 20 pt} (7) .If we differentiate equation 7 and equate to 0 ,two roots of quadratic equation are either local minima and maxima or vice-verse of equation 7 and one of the root of equation 7 will be in this interval. We can search this root by binary search [ why ? because either the function will be increasing or decreasing in this interval ]. After getting one root , divide the equation 7 by this root [ see factorisation ] and get the other 2 roots of quadratic equation by closed form . The time limit for this problem is very tight so Haskell solution got time limit exceed while c++ passed. Accepted code

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;

ll fuN( ll a , ll b , ll c , ll d , ll x ) 
	{

		return ( ( a * x + b ) * x + c ) * x + d ;  
	}
  
ll bsearch( ll a , ll b , ll c , ll d , ll lo , ll hi )
	{
		ll mid ;
		while( lo < hi ) 
		{
			mid = ( lo + hi ) >> 1 ; 
			ll f = fuN ( a , b, c , d , lo );
			ll s = fuN ( a , b, c, d , mid ) ; 
			if( ( f > 0 && s > 0 ) || ( f < 0 && s < 0) ) lo = mid + 1 ;
			else hi = mid ;
		}

		return lo;
	}

void solve ( ll n , ll phi , ll sigma ) 
	{
		
		ll a = 2 , b = 2 * n - phi - sigma , c = sigma -  phi - 2 , d = -2 * n ;
		ll dis = ( ll ) sqrtl( ( 4 * b * b - 12 * a * c ) * 1.0 ) ;
		ll low =( ll )  ceill( ( -2 * b - dis ) / ( 6.0 * a ) );
		ll high = ( ll ) floor ( ( -2 * b + dis ) / ( 6.0 * a ) );
		ll r = bsearch (  a , b , c , d ,  low , high ) ; 
		ll d1 = -( b + r * a );
        	ll d2 = ( ll ) sqrtl ( b * b  - 4 * a * c - 2 * a * b * r - 3 * a * a * r * r ) ;
		ll r1 = ( ll ) ( ( d1 - d2 ) / ( 2 * a ) ) ;
        	ll r2 =  ( ll ) ( ( d1 + d2 ) / ( 2 * a ) ) ;
		printf("%lld %lld %lld\n", r1 , r , r2 );

	}

int main()
	{

		int t;
		ll n , phi , sigma ; 
		for(scanf("%lld",&t ) ; t > 0 ; t--) 
		 {
			scanf("%lld %lld %lld", &n , &phi , &sigma );
			solve ( n , phi , sigma );
		 }
	}

Haskell code which got time limit exceed. If your Haskell solution is accepted then please let me know.

import Data.List
import Data.Bits
import Data.Maybe
import qualified Data.ByteString.Char8 as BS

bSearch :: ( Num a , Integral a , Bits a ) => [ a ] -> a -> a -> a
bSearch [ a , b , c , d ] low high = helpBsearch low high where 
	helpBsearch lo hi 
          | lo >= hi = lo  
	  | fuN lo * fuN mid > 0 = helpBsearch ( succ mid ) hi
	  | otherwise = helpBsearch lo mid
	  where mid = shiftR ( lo + hi )  1
		fuN x = ( ( a * x + b ) * x + c ) * x + d  



solve :: ( Num a , Integral  a , Bits a ) => [ a ] ->  BS.ByteString
solve [n , phi , sigma ] = roots    where 
	( a , b , c , d )  = ( 2 , 2 * n - phi - sigma ,  sigma - phi - 2 , -2 * n )
	dis =   sqrt . fromIntegral $ 4 * b ^ 2 - 12 * a * c 
	low =ceiling $ ( ( fromIntegral $  -2 * b  )  - dis  ) / ( fromIntegral $  6 * a  )
	high = ceiling $  ( ( fromIntegral $  -2 * b  )   +  dis  ) / ( fromIntegral $  6 * a  )
	r = bSearch [ a , b , c , d ]  low  high 
	d1 = -( b + r * a ) 
	d2 = truncate.sqrt.fromIntegral $ b ^ 2 - 4 * a * c - 2 * a * b * r - 3 * a ^ 2 * r ^ 2 
	r1 = div ( d1 - d2 ) ( 2 * a ) 
	r2 = div ( d1 + d2 ) ( 2 * a )
	roots =  BS.append  ( BS.append ( BS.append ( BS.append ( BS.pack.show $ r1 ) ( BS.pack " " ) ) ( BS.pack.show $ r ) ) ( BS.pack " " ) ) ( BS.pack.show $ r2 ) 


readInt :: BS.ByteString -> Integer
readInt = fst . fromJust . BS.readInteger  


main = BS.interact $ BS.unlines . map ( solve . map readInt . BS.words ) . tail . BS.lines  
Advertisements

August 1, 2011 - Posted by | Programming | , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: