# Factorization of the semi-palprime $N = pq$

I define semi-palprime be a prime number that remains the prime when its digits are reversed, like $p = 13$, and its mate is $q = 31$. I know that number $N$,

$N = \\40276504015957241212219140055284581853797537049211403507316894593383\\ 47457987912639871372112187693426311212748251225732519905589136273168\\ 20318858996928988487350273731350467362899934942766591227002091985684\\ 14312802147969417515545625068960627407674722275954470998513985249290\\ 2998963539890226770447590949818014983$

is the product of one semi-palprime number $p$ and its mate $q$, how I can factorize $N$?

• Does this have any cryptographic applications?
– otus
Aug 11, 2015 at 7:44
• @outs I don't know, but you can suppose that some app generate RSA keys with this feature, $p$ and $q$ such that $p$ is semi-palprime number and $q$ is its mate. Now you want to break that RSA key, and I have asked how.
– Lisbeth
Aug 11, 2015 at 7:58
• @outs You are right, but I think that finding that prime is an algorithmic way and I need an optimized algorithm to find $p$ and $q$, coz the digits of $p$ are reversed in $q$ and we know the product of them, $N$.
– Lisbeth
Aug 11, 2015 at 8:30
• I'm voting to close this question as off-topic because this is a question about recreational mathematics, and not crypto at all (not all factoring questions are cryptographically interesting) Aug 11, 2015 at 11:31
• This could be cryptographically interesting if 1) the "semi-palprime" pair was easy to find and 2) if it wasn't significantly easier to factor. Unfortunately that doesn't seem the case, but I guess it can be called crypto (as in: analyzing a new generation system for RSA key pairs). We've seen worse ideas here :) Aug 11, 2015 at 12:12

You work at both ends towards the middle; if you know the lower $n$ digits of $p$, you can immediately deduce the lower $n$ digits of $q$, as $q \equiv N p^{-1} \pmod{10^n}$
Similarly, if you know the upper $n$ digits of $p$, you have a bound on the upper $n$ digits of $q$, as if you know that $p$ is in the range $(p_0, p_1)$, then $q$ must be in the range $(N/p_1, N/p_0)$
So, look through the possible values of the lower two digits of $p$, deduce the corresponding lower two digits of $q$. Now, because the primes are mirror images of each other, this implies the upper two digits; check to see if the corresponding upper digits are compatible. Some will be, most won't be; reject the possibilities that aren't.