#!/usr/bin/perl

# Get factorization from modulus + public exponent + one CRT exponent
# Copyright 2014, mancha

# [Sample RSA parameters]
# n=54299051326517
# e=65537
# d=27282496541453
# p=7368787
# q=7368791
# e1=1134827
# e2=1062643
# coeff=1842197

use Math::BigInt;

## 1. Known information
# Public exponent
$e = Math::BigInt->new('65537');
# Modulus
$n = Math::BigInt->new('54299051326517');
# DP: d (mod (p-1))
$e1 = Math::BigInt->new('1134827');

## 2. Arbitrary payload
$m = Math::BigInt->new('1337');

## 3. Recovery
$c = $m->copy()->bmodpow($e,$n);
$mp = $c->copy()->bmodpow($e1,$n);
$diff = $m->copy()->bsub($mp);
$prime = $diff->copy()->bgcd($n);

printf("Here's one of the primes: %s\n",$prime);