4
$\begingroup$

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$?

$\endgroup$
7
  • $\begingroup$ Does this have any cryptographic applications? $\endgroup$
    – otus
    Aug 11, 2015 at 7:44
  • $\begingroup$ @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. $\endgroup$
    – Lisbeth
    Aug 11, 2015 at 7:58
  • $\begingroup$ @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$. $\endgroup$
    – Lisbeth
    Aug 11, 2015 at 8:30
  • 3
    $\begingroup$ 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) $\endgroup$
    – poncho
    Aug 11, 2015 at 11:31
  • $\begingroup$ 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 :) $\endgroup$
    – Maarten Bodewes
    Aug 11, 2015 at 12:12

1 Answer 1

Reset to default
6
$\begingroup$

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.

For the possibilities that are, then go through the possibilities for the third digit; repeat the execise until you meet in the middle.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.