Forum

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: DarkFibre on July 28, 2011, 11:53 p.m.

Well, I found optimized code for Fermat's method, implemented it in python and started it Monday after testing it on a small semiprime. It's been 72 hours, no answer yet. I'm getting the idea this is the wrong way to go but running out of ideas. Or I screwed up my code somehow. Or python has more evil quirks… I keep running into those.

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: DarkFibre on Aug. 8, 2011, 9:19 p.m.

I was really hoping it would find a solution while I was on travel but it's now been running 2 weeks with no solution. Time for a new plan…

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on Aug. 8, 2011, 9:20 p.m.

What method are you running?

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: DarkFibre on Aug. 8, 2011, 9:45 p.m.

The Fermat method I mentioned above

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on Aug. 8, 2011, 9:45 p.m.

This is really strange, there has to be an error!

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: mmisc on Aug. 8, 2011, 11:28 p.m.

if i remember correctly solving this challange with the correct algorithm dosent took one second of cpu time with a up to date cpu

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on Aug. 8, 2011, 11:45 p.m.

Ive had cryptool use 6 different algorithms on it, even used a known digits attack with no luck. Ive got many number theory books and so have access to nearly every factoring algorithm known to man, yet none of them seem to work! Im convinced that fermat is the right way to go but after searching about 15 million primes either side of the square root of N, I got nothing. I think there is some sort of error here!

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on Aug. 13, 2011, 12:59 a.m.

Ok, this is getting ridiculous now.

I have put this semiprime into a few professional factorising programs and none of them come up with anything (each time I run for quite a while and am left waiting at the elliptic curve search stage).

There just has to be an error here!

If there primes were as close as is made out on here then all of these programs would find the factors. It cannot be a coincidence that cryptool's search of 6 algorithms, DarkFibre's 2.5 week run of Fermat factorisation, my maple search AND all of this other software come up with absolutely nothing.

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: Gummiboot on Aug. 13, 2011, 1:41 a.m.

My hand-made Python fermat need less 3 minutes, my C-programm less one second.
Code your tools your self, thats better!

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on Aug. 13, 2011, 1:50 a.m.

You used basic Fermat (i.e. find a such that a^2 - N = b^2 for some b)?

I made my own version of this in maple, I even modified it in two different ways…it still turned up nothing (I was proud because I can barely program anything).

DarkFibre also made a very efficient Fermat factorisation algorithm and as I say, after 2.5 weeks of running it still turned up nothing.

I am convinced something has happened to the number that has made it extremely difficult to factorise. Could you please check that the number remains the same and still factorises easily?

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: Gummiboot on Aug. 13, 2011, 3:14 a.m.

Yes I use the basic fermat.
Perhaps your start value is not optimal.

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on Aug. 13, 2011, 11:04 a.m.

Well if the prime factors are close then the optimal start value for a is:

floor(sqrt(N)) + 1

so that b is small, making (a+b) and (a-b) very close.

I think there is a problem with maple's arithmetic when the numbers are this small.

My program tests whether sqrt(a^2 - N) is an integer and this process seems to not be working properly. This could be why Fermat isnt working properly for me.

e.g. I put in something big like this:

type(floor(410769987697640686545912084791765927084789886769073097629387489698608610868962987498798888888827870987048708680608670827897897987986498698309092609690609760967290769376397649609692697693769696976976976976)^(1/2), integer);

and get "false", when clearly the answer should be "true" (since the floor of something is always an integer). I have no idea how to get around this.

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on Aug. 13, 2011, 1:17 p.m.

I am successful!! Finally.

Turns out maple doesnt like square rooting big numbers and checking whether they are integers, hence my program was only pretending to work.

I had to use isqrt(N) cleverly in order to get around this. Once I did this, it worked within seconds.

Then maple has a problem working out c^d mod N because of the size of d. I found a way round this too.

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: argh on Aug. 13, 2011, 1:25 p.m.

Be careful here. If you place the brackets like that, floor calculates the floor of the integer, and not of the square root, as you probably intended. So Maple actually was right. :)

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on Aug. 13, 2011, 1:43 p.m.

Well I did try it both ways anyway, putting brackets around everything that I wanted flooring.

It would stop giving me the numerical values when the numbers got so big, I think this made a problem.


Currently 24 guests and 0 members are online.
Powered by the CrypTool project
Contact | Privacy | Imprint
© 2009-2024 MysteryTwister team