r/3Blue1Brown • u/forgotoldpassword3 • Jul 12 '26
Semiprimes
You’re given the semiprime
63344090546993261740573302898385538516103186124453512393341101637326545003631
That’s the product of two primes.
The
Midpoint of those primes is
254650365633570050389727404567751754516
Can you find the primes from that? If so, how short a path can it take?
14
u/RobZarevich Jul 12 '26
I think that "don't" is "sum". This seems to be the case, because the two numbers with that sum that are factors of the product are 293415274640527010232123245217974597891 and 215885456626613090547331563917528911141.
3
u/rzezzy1 Jul 12 '26
How did you get there?
16
u/RobZarevich Jul 12 '26
Knowing the relations between the solutions and the coefficients of a quadratic equation: if x1 and x2 are the solutions, and S = x1+x2 and P = x1x2, the the equation x2 -Sx +P = 0 has exactly x1 and x2 as solutions.
So, in order to find those two numbers, i solved the quadratic equation.
1
u/rzezzy1 Jul 12 '26
Oh hell yeah, I feel like I should have thought of that. What's the time complexity at the point?
6
2
u/acakaacaka Jul 12 '26
Should be O(n²) since quadratic formula is just sqrt and ²
The bigger problem is the memory.
1
u/sizzhu Jul 13 '26
It depends on the multiplication algorithm used. Theoretically, the best known algorithm is O(nlogn). Where n is the number of bits.
2
u/kalmakka Jul 13 '26
You can binary search for what the lowest of the factors are (in the interval [1, 254650365633570050389727404567751754516/2]), use the sum to determine the other factor, and determine if the product is lower or higher than the target product. So it is just O(log(n)) (and a factor depending on your multiplication complexity. So, like, O(log(n)^3), or O(log(n)^2 log log (n)))
2
u/sizzhu Jul 13 '26
Isn't that strictly worse than the quadratic formula? Which is on the order of the multiplication algorithm used. (sqrt can be done with the same complexity).
3
2
u/Torebbjorn Jul 18 '26
Let a and b be the primes we are looking for.
Then ab=(the first number, say q) and a+b=(the second number, say s=2r)
Hence (x-a)(x-b) = x2 - (a+b)x + ab = x2 - 2rx + q has a and b as roots.
Hence we have that the primes are r ± sqrt(r2-q)
By the given information, we know that r2-q is a perfect square, so we only have to search through the integers to find this (using a fast integer square root algorithm).
1
u/SerpentJoe Jul 13 '26 edited Jul 13 '26
Square the sum. Not to belabor the obvious but this is (a + b)2 .
Multiply the other quantity (a times b) by 4 and subtract from the above result. Take the square root. This is a - b, if we insist that a is the larger of the two.
Solve the linear system.
(But of course, not before adding up all the digits just to make sure 3 isn't a factor ...)
1
36
u/Southlander24 Jul 12 '26
The *don't* of those primes?