-2
$\begingroup$

So I was sitting on an algorithm I thought up at school, and just decided to implement it. And it worked for what I wanted - but I don't know what this is worth.

I broke apart a 2048 private key for the $N$, $Q$, and $P$.

So for $N$:

CC0202236A4B976D7FC217BEF43F6C3EAC719BD97E1092059F972D2C993F1492
5835001F0CC38DC647311A77DFAA76C6549177D7317F88FA3001FF62F6F7F6AD
2D409516C78BE52105B34EFBBEDB809DBF8F66B278CFC24B2DEDB55322AACA04
405A4E6D03452B65A5403321037129369E34A03EC7096259B901CA3E1B944A58
D52D23DBE53E4EFD1EB3600AD4B656E9EF436B3EAF749C40538F47373153C9DE
4D49B8FD8199E0A02178F35112DA0498420414B9411449A1AB7389089CDABD18
1BE6B6A75E25D4F3B841930579800DA84BA364769EAC7BF1A322600502BB8540
E7DEDAC7406F942FFB37B83379C9213CA3650031F1780CB25A037971D7EEAAFB

I can divide $N$ with $P$:

D516C8D981FB9AC371FD118A72C321BC4017EAEE3B2052E57F255C5ACAEC18AC
CA7BB4EDA490857BA0728FAF55DD3EF418669D0D474B27A23F56B67905326D6D
2DE99FCA4BA9B7693DDAFB72447C81E6B3C11D0B2C80877956A832006675D13B
38E226DBDCC18C7127E1699EF64FDA749F5249FB4B50FC4E1AC669ED32947729

and correctly I get $Q$:

F51711DDE37AA3CF475D7ABF3549E084B723BDA65BEFDE814FF4D9FC4787E3E6
27077108677D2FF2C2268F8344E71F40FE3381616BB9F69300139C3D01BDA92D
B0AA6A4CB668C866359E327D89C0FFC31B3B88FECC4E9E1B30957EDCFC7069C0
4BDEAC10A5EF0CDBCFD78225AEBF6E5140BD93B69AAC9323F540086136834983

I then divide $N$ by $Q$, and $I$ get $P$.

Is this "worth" anything?

I know "Factoring" $N$ may take infinitely longer to do, but is "division" worth anything by itself?

$\endgroup$
  • 3
    $\begingroup$ Large integer division is pretty standard and depending on the details quite "boring". But nonetheless it's nontrivial and as such it is impressive that you found out how to do it all by yourself in school! $\endgroup$ – SEJPM Dec 31 '16 at 19:58
  • $\begingroup$ Knuth's "The Art of Computer Programming" has efficient integer division algorithm, implementing it is not an easy programming exercise. $\endgroup$ – kludg Jan 1 '17 at 18:33
9
$\begingroup$

Unfortunately you haven't made a scientific discovery.

One of the places where large integer division is required is when testing for prime values. Primality tests are required to find real prime numbers within a set of candidate primes. So to find $p$ and $q$ large integer division is already required.

That said, doing such a big calculation efficiently requires some interesting techniques. Definitely go on and study Discrete Math (and Computer Science and algorithms) if you're interested in these kind of things. Then you can always progress to Theoretical and/or Practical Cryptography once you've mastered those.


Just to show that this can be done using regular libraries (in Java):

import java.math.BigInteger;

public class BigNumberDivision {

    private static final BigInteger N = new BigInteger("cc0202236a4b976d7fc217bef43f6c3eac719bd97e1092059f972d2c993f14925835001f0cc38dc647311a77dfaa76c6549177d7317f88fa3001ff62f6f7f6ad2d409516c78be52105b34efbbedb809dbf8f66b278cfc24b2dedb55322aaca04405a4e6d03452b65a5403321037129369e34a03ec7096259b901ca3e1b944a58d52d23dbe53e4efd1eb3600ad4b656e9ef436b3eaf749c40538f47373153c9de4d49b8fd8199e0a02178f35112da0498420414b9411449a1ab7389089cdabd181be6b6a75e25d4f3b841930579800da84ba364769eac7bf1a322600502bb8540e7dedac7406f942ffb37b83379c9213ca3650031f1780cb25a037971d7eeaafb", 16);
    private static final BigInteger P = new BigInteger("D516C8D981FB9AC371FD118A72C321BC4017EAEE3B2052E57F255C5ACAEC18ACCA7BB4EDA490857BA0728FAF55DD3EF418669D0D474B27A23F56B67905326D6D2DE99FCA4BA9B7693DDAFB72447C81E6B3C11D0B2C80877956A832006675D13B38E226DBDCC18C7127E1699EF64FDA749F5249FB4B50FC4E1AC669ED32947729", 16);
    public static void main(String[] args) {
        BigInteger q = N.divide(P);
        System.out.println(q.toString(16));
        // prints: f51711dde37aa3cf475d7abf3549e084b723bda65befde814ff4d9fc4787e3e627077108677d2ff2c2268f8344e71f40fe3381616bb9f69300139c3d01bda92db0aa6a4cb668c866359e327d89c0ffc31b3b88fecc4e9e1b30957edcfc7069c04bdeac10a5ef0cdbcfd78225aebf6e5140bd93b69aac9323f540086136834983
    }
}

Or, in case you have access to the bc calculator on a POSIX system (Linux, Apple, Cygwin etc.) the one liner:

echo 'obase=16;ibase=16;\
CC0202236A4B976D7FC217BEF43F6C3EAC719BD97E1092059F972D2C993F1492\
5835001F0CC38DC647311A77DFAA76C6549177D7317F88FA3001FF62F6F7F6AD\
2D409516C78BE52105B34EFBBEDB809DBF8F66B278CFC24B2DEDB55322AACA04\
405A4E6D03452B65A5403321037129369E34A03EC7096259B901CA3E1B944A58\
D52D23DBE53E4EFD1EB3600AD4B656E9EF436B3EAF749C40538F47373153C9DE\
4D49B8FD8199E0A02178F35112DA0498420414B9411449A1AB7389089CDABD18\
1BE6B6A75E25D4F3B841930579800DA84BA364769EAC7BF1A322600502BB8540\
E7DEDAC7406F942FFB37B83379C9213CA3650031F1780CB25A037971D7EEAAFB / \
D516C8D981FB9AC371FD118A72C321BC4017EAEE3B2052E57F255C5ACAEC18AC\
CA7BB4EDA490857BA0728FAF55DD3EF418669D0D474B27A23F56B67905326D6D\
2DE99FCA4BA9B7693DDAFB72447C81E6B3C11D0B2C80877956A832006675D13B\
38E226DBDCC18C7127E1699EF64FDA749F5249FB4B50FC4E1AC669ED32947729' | bc
| improve this answer | |
$\endgroup$

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.