[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 10 KB, 200x181, 1307550075275.jpg [View same] [iqdb] [saucenao] [google]
6158969 No.6158969[DELETED]  [Reply] [Original]

First year Informatics student here.
Since there is no formula for integer factorization,
what are the methods/procedures for doing so?

I mean, how those fuckers managed to factorize

74037563479561712828046
79609742957314259318888
92312890849362326389727
65034028266276891996419
62511784399589433050212
75853701189680982867331
73273108930900552505116
87706329907239638078671
00860969625379346505637
96359 into two primes?

http://en.wikipedia.org/wiki/Rsa_challenge

>> No.6158981

>$200k given in order to find the solution to some ridiculously-long number
Why? Who's paying for it in the end?

>> No.6158984

>>6158981
In the end I cannot precisely tell you how gave money for this, but the pragmatic goals for this whole 'contest' was to find fast methods of factorization (critical thing for modern computer science and global safety --> cryptography works on this shit all the time) or at least improve already used. Though, there are ways of fast factorization, but on quantum computers, which don't exist yet.

>> No.6158990

>>6158984
Fair enough. I believe they have made something like a 2-qubit quantum computer, which is interesting.

>> No.6158994

>>6158990
no, they've gotten into the tens of quibits.

>> No.6158995

>>6158994
oh the magazine I've read was old, that's even better.

>> No.6158997

Can't you just brute force it?

>> No.6158998

>>6158997
They've made it in month. Brute force would probably take years. Besides, what's the method used by brute force then?

>> No.6159004

>>6158998
let p(n) be nth prime:
N number

if N % p(n) == 0: N=N/p(n); save p(n)
else n+1

>> No.6159008

>>6158998
for prime in primelist:
sol = mod(number, prime)
if sol == 0:
goodPrime = prime
break
otherPrime = num/goodPrime

>> No.6159015

>>6158969
>Since there is no formula for integer factorization, what are the methods/procedures for doing so?

Prove that P=NP.

>> No.6159019

>>6159004
>>6159008
>>6159004
>>6159008
Yes of course, but it won't do the trick here. Too much processing time and working space requirements. Who would pay 20k for just appling b=c/a?

>> No.6159032

>>6159015
>>6159015
Don't you logic on me, you know what I meant.
There is no fast and efficient algorithm for factorizing big numbers that can be applied in modern computers, so what are methods of doing it manually?

>> No.6159039

>>6159015
P=NP
N=P/P
N=1
P=1*P
P=P
fuck off.

>> No.6159135

Actually, it's super easy for a computer.

It's done using a thing called Fermat's factorization method. We assume that the number, let's call it n, is odd (since otherwise you can just divide it by two). Fermat showed that you can always factor an odd number into the difference of two squares. So you check n - x^2 =y for every x above sqrt(n) and some other number (twice n? I don't remember), and see if y is a square. If is it, congratulations! You have factored n into the numbers x+y and x-y.

>> No.6159139

>>6159019
As he said.
Brute force would take years.

>> No.6159153

>>6159135
At least, more efficient than some methods mentioned so far

>> No.6159183

>>6159135
pseudo-code?

>> No.6159185

>>6159032
If you could do it manually, the computer could do it too. Thus, there is no such way.

>> No.6159193

>>6159183
Computers can't work heuristic (yet). Humans can. Proof: check on link I gave, that actually people managed to factorize some numbers and won the prizes, even though they didn't find efficient algorithm.

>> No.6159616

>>6159039
There are not operators. It's just an equality.