1wayfx challenge
Craig Feinstein
as to how to solve this problem?
http://1wayfx.com./21012/index.html
Craig
Tom St Denis
I don't get the challenge...
f(x) = 1063372.... + x*0
Is a solution to the problem. Maybe if the person specified the
algorithm ...
Anyways... nice plug "mysterious reader who is in no way affiliated
with the given domain/company".
Tom
Pubkeybreaker
given F (....) [a function of 5 variables) (capital F; it is
important)
and an integer a
solve f5(n) = a (lower case f with the digit 5 added]
But the problem never states what F is, what f5 is or what n is.
Is n an integer?
an integer vector? etc. etc.
It is nonsense.
Craig Feinstein
It's not gibberish because when you click on 'F={f1,f2,f3,f4,f5}' you
get its definition.
Craig
Craig Feinstein
I would have thought that by now, someone would have come up with a way
to break this code. I guess the wise men and women of sci.crypt aren't
as brilliant as I thought.
Craig
Tom St Denis
You guessed right. Move along, nothing to see here.
Tom
Alex
> Has anyone tried to solve this problem or anyone have any suggestions
> as to how to solve this problem?
>
> http://1wayfx.com./21012/index.html
Had a look at it today and I've just finished off the majority of the
optimisations that I can think of (mainly to my xor() and zb()
functions).
The LSB of f3 must match that of f5. Since the given a is odd (...809) we
can skip any cases where m (f3) is not odd. In some tests on random
n's this represents about 18% of cases.
This only saves a tiny amount of time as computing f4 and f5 are nigh
on trivial in comparison to f2 and f3.
Of course, some further analysis of inputs/ouputs may provide some other
useful restrictions but I have not done this at all. I've simply gone
for a brute force approach after implementing the algorithm.
My program can check around 4500 values of n a second, where:-
the program has 100% CPU usage of a 2GHz Athlon.
n^3 is 409 bits (similar size to the target value provided)
To calculate f5(n) for n=1 to 1000000 it takes my program roughly 25 secs
on the above machine.
As for bounding the searchspace, the only limitation I can think of is that
n must be at least 2^136, otherwise it would be impossible for the 409th
bit to be set in f5(n).
f3(n) is limited by 0 < f3(n) < n^3
And since:-
f4(n) = n^3-f3(n)
f4(n) can have any value between 1 and (n^3)-1
And since:-
f5(n) = f1(n) xor f4(n)
I cannot see any upper bound for f5(n). n^3 could have 2048 bits but still
reduce to the desired 409 bit value of a given.
If I limit my algorithm to just 409 bit values for n^3 that means I have
to check every number from:-
n^3 = 2^408
n = 2^136
n = 87112285931760246646623899502532662132736
to
n = 109754602749885759373373565566886695734313
for this n, n^3 > 2^409
At a speedy 4500 a second on my single 2GHz Athlon this will take roughly
2^97 or 1.6E29 years.
In other words, to get it done in 1 year would require each of Earth's
6 billion residents to go out and buy 26,591,968,753,083,498,608 2GHz
Athlon PC's *EACH*.
I'll see if I can clean up my code so people can see how I've implemented
it, if anyone is interested that is. It's less than 200 lines of C.
I might also see if I can find any clashes. In a quick test each
f5(n) for 1 < n < 1,000,000 is unique. But I'm guessing there is a
collision somewhere.
Ta,
-Alex
Craig Feinstein
Alex, thank you for your comments. The inventor of the function claims
that the only possible way to find a solution is through a
brute-force-type search. Do you think this is the case?
Craig
Jean-Luc Cooke
> I would have thought that by now, someone would have come up with a way
> to break this code. I guess the wise men and women of sci.crypt aren't
> as brilliant as I thought.
'P is not NP' (pdf)
a solution to the 'P vs NP Problem'.
...
wow. Brilliant.
JLC
--
Jean-Luc Cooke
> I would have thought that by now, someone would have come up with a way
> to break this code. I guess the wise men and women of sci.crypt aren't
> as brilliant as I thought.
> Craig
Could you explain the ZB(n^3 xor n^2) function?
JLC
--
uk...@greenbank.org
n^3 xor n^2 should be obvious.
ZB(n) is the number of significant zero bits in a binary representation
of n, ignoring insignificant leading zeroes.
ZB(1) = 0 (1 in binary is 1)
ZB(2) = 1 (2 in binary is 10)
ZB(3) = 0 (3 in binary is 11)
ZB(4) = 2 (4 in binary is 100)
ZB(5) = 1 (5 in binary is 101)
ZB(6) = 1 (6 in binary is 110)
ZB(7) = 0 (7 in binary is 111)
ZB(8) = 3 (8 in binary is 1000)
etc.
That help?
-Alex