TI-Nspire Key Brute Forcer

[DJ Omnimaga]

Yeah I understand, not to mention there is another topic too. But yeah as suggestion, checking the topic's first post is generally a good idea in some cases. Other times it isn't because it is not updated, but some authors update the main info there.

[XVicarious]

It doesn't look to me like he updated it, oh well. I know now

[z80man]

I think it should also be a small range that a server assigns you at a time. Running nonstop on my computer http://www.omnimaga.org/index.php?topic=6621.msg120921#msg120921 with four instances it would take me four days to get through a 32 bit range on the C# version. For the asm version I am expecting about twelve hours on my system.

[phenomist]

What algorithm are you using? ECM has breezed through a 64 bit range in less than 2 hours.

Spoiler for ECM curve progress:

* = Paused Progress

Spoiler for Curves 0 - 10000:

0-1000 - phenomist
x0yy: finished, x1yy: finished, x2yy: finished, x3yy: 33% done*, x4yy: done, x5yy: done, x6yy: 37% done, x7yy: ns, x8yy: ns, x9yy: ns

1000-2000
2000-3000
3000-4000
4000-5000
5000-6000
6000-7000
7000-8000
8000-9000
9000-10000

10000+ (once assigned, categories will be written out)

Spoiler for curve = 10000+:

Starting at 421337: phenomist (up to 421345)

[DJ Omnimaga]

How many did SirCmpwn's program went through in the same amount of time compared to yours?

Also, from what I gather, Calc84maniac rewrote his program in assembly, but I could be wrong.

[phenomist]

Well, to be precise, I only found the program; I obviously did not write the (really good) factorizer in the link.
(Rehash: link is here -> http://www.alpertron.com.ar/ECM.HTM )

Spoiler for key in decimal:

137426454337521899137502452525605466748829534697526357946510356073439963309278587906732336287048350 193565270671049611558935534759741894429581138110991019864818898792610752419053602832785246554297841 481080233597667469592742563152706207467933515159107380059434427511231769817853007350965081930222294 271540538551

I accidentally truncated the key in an early test run to 42 digits (about 120-ish bits); it factored (or rather didn't factor) the prime in under a second.

Also, there's no way I can directly compare speed otherwise, but I'd say that it'll run somewhere on the magnitude of millions of times faster, if the current algorithm is a straight up divide this, add by two algorithm.

[Lionel Debroux]

I don't know if this has already been asked, but why not write it in x86 asm or C?

Yes, it has been suggested by myself on page 6, and such a TF program was even written and published on Omnimaga, by Tribal and myself, months ago

phenomist, ECM is only good for finding small factors. It's roughly as extremely unlikely to find a 512-bit factor as TF is... IOW, you too are wasting your CPU time.


I stand corrected, I failed to communicate in my previous post, on page 6. That people make a bad independent reinvention of the wheel, without having consulted the background contained in other previous topics (or understood it, as DJ is arguing - I disagree, see below), and make everyone waste time (CPU time or explanation time) was no valid reason for the TL;DR part. Again, this is no excuse, but if some big names in the integer factoring had commented on the topic, now that would have been bashing, I can tell you... Although they'd probably have chosen to completely ignore 1) anyone trying to TF a RSA key and 2) the misguided waste of CPU time due to the sub-par implementation we're talking about here.
It's sad to see people focusing on several words at the end of a post containing > 90% of useful content (I could just have posted the TL;DR part, Kofler's style - you know that he's less patient than I am). It's sad to see that they seem to keep working in the wrong direction (the C# program) or reimplementing the wheel yet another time (for the fifth time in two days: on the Omnimaga forum, there's already a C program started by Tribal and optimized by myself, with manual resume support, I explicitly mentioned it in my previous post - so there was nothing to understand, just use the program) - i.e. I totally failed, because my post has had the opposite of the intended effect.

Anyhow, it's probably the last time I'm trying to help on Omnimaga wrt. factorization of the Nspire keys. I've already spent too much time trying to explain things. I'm aware that not everybody reads everything on Omnimaga - for one, I don't - but I really feel I've wasted my time.


BTW, could someone explain me how I attempted to start a language war by pointing the well-known, common sense fact that C#, and other languages of the same class, are not the best fit for heavy number computation tasks ? That might help me for the next time I'm participating in a discussion here.

[z80man]

@Lionel Debroux you are trying to start a language war.

by pointing the well-known, common sense fact that C#, and other languages

If you see here by calling this a common sense fact you are being offensive to people who code in C# and are involved in this project. You are not providing any reasons and are just discouraging people from taking part in this project. You also blame others for not reading your post fully when it seems that you did not fully read the topic. If you had you would see that the C# program is only temporary until Calcdude84SE codes the optimized asm version. C# was chosen as that is the language Sir best programs in. Brooom is also in the process of creating a server to streamline the factoring process. So far all you have contributed is a negative atomsphere and this will not be tolerated any longer.

[Lionel Debroux]

Nope, I did not miss the "While a better program is worked on" part. But the thing is, a better program than this one did already exist, although nobody seemed to remember, and, as I reminded, I have worked on it.
And z80man, I did provide reasons for why there were better fits than C# or languages or the same class
Also, note that I haven't written that there wasn't any way to do a better TF program than the existing program that Tribal and I worked on

EDIT: at z80man's request, adding link to the topic containing the GMP-based C implementation made by Tribal and I: http://www.omnimaga.org/index.php?topic=3639.0 / http://www.omnimaga.org/index.php?action=topicattach;topic=3639 .


As I already wrote on IRC and above, I don't think that my warning is undeserved. It was, however, unfair, insulting (even slanderous ?) that a number of you vilified me for not having worked on better TF'ing programs (despite my explicit mention, in that very post, that I did !)... This is why my first reaction on IRC, this morning, was "Um, are you nuts ?".
We're in a situation where both "you" (the participants to the topic) and me feel doubly insulted. And as AOC posted after the initial version of my post, let's calm down. On my side, I've already posted my apologies.

[Art_of_camelot]

@All:Please calm down a bit guys. I don't see any evidence of anyone trying to start a language war. If a tool has already been written in a more efficient language, I don't see pointing that fact out as trying to incite a language war.

@Lionel: I understand your frustration seeing as you have contributed in a previous topic about the same thing and helped the C implementation of a factoring program. Just, be sure not to be rude.

[KermMartian]

As a computer scientist and electrical engineer with two degrees and two more in progress, I completely back Lionel on this.  The state-of-the-art involves research labs with millions of dollars of funding and massive superclusters working on this problem; your approach is naive and lacks their experience (no offense, that's the fact; naive in its computer science definition: "taking the most apparent route, which is often the least optimized").  To put it harshly and bluntly, if teams with dozens or hundreds of years of research experience between them have shown this problem to be prohibitive with large clusters and extremely well-written C code, I'm afraid that an amateur implementation in C# is not going to cut it.  I think it was pretty clear that Lionel was looking out for your best interests and trying to save you frustration, electricity, and computer load.  His post was well-written, knowledgeable, and I think those who read it in its entirety should have taken no offense from it.  Regarding the language issue, the speed of C# due to overhead compared with well-written C is a well-documented academic fact.

Cheers.

[DJ Omnimaga]

Yeah, the issue was simply the final part of the post, which was against Omni rules (especially the "facepalm" comment). When a post contains one harsh part, for many people it will pretty much blind them from the rest of the post content, and I feel that a large useful post is not an excuse to append a small rude comment at the end. As for the language comment I guess I misinterpreted it as a language war starter, but we had several of them recently by various people so I guess it can be hard to make the difference after a while. I also had to deal with several language wars before on another game-related calculator forum and yAronet is historically known to have them too (eg: Goplat's port of Java to the TI-Nspire was heavily bashed by various people, even if the project was by the very one who wrote a TI-Nspire NES emulator and a computer TI-Nspire one).

That said, calc84maniac came to the rescue with his ASM alternative, but otherwise we would be stuck with a C# version, since no one else knew how to write one in ASM or C. I am hoping that Lionel's method of factoring the key will be implemented in the ASM version or that his own program will be used, if people can actually find it in the 3 threads. Basically, for now, it was either an innefficient C# method, or nothing.

I apologise for misinterpreting the C# comment as language war and accusing you of not having contributed any program for this, but remember to be careful about the tone of your posts on Omnimaga. Just remember also that there are people who are more sensitive than others and when visiting this forum they might be like:

PotentialHardcoreTiProgrammer: "Wow look at that thread, look what kind of remark this guy say to others. Let's find another forum."
RandInt(1,2
If Ans=1:Then
*signs up elsewhere*
*suggests friends to avoid Omnimaga*
Else
*quits the community after failing to find another board*
End

We won't single out/treat as inferior being this group of people, like I saw happen on many other TI sites in the past.  Anyway you apologised for the that so that's good.

[Lionel Debroux]

I am hoping that Lionel's method of factoring the key will be implemented in the ASM version or that his own program will be used, if people can actually find it in the 3 threads.

Well, DJ, I provided a direct link to the source code in my previous post
The topic is http://www.omnimaga.org/index.php?topic=3639.0 , and the attachments are http://www.omnimaga.org/index.php?action=topicattach;topic=3639 . And maybe admins have a quick way to find the post corresponding to a given attachment ?
Quoting myself:

note that I haven't written that there wasn't any way to do a better TF program than the existing program that Tribal and I worked on

I know of the algorithm you've posted - but it goes for both myself and yourselves
On the one side, there are two improper words in the "TL;DR" summary of my post, for which I apologized.
On the other side, there's a groundless personal attack, sent by some of you - among which some moderators - against me. I have actually spent some of my free time working on something to help with TF'ing the Nspire key - unlike most of those who posted that attack and down-rated my post.
So, please apologize on your side, and let's go forward together. Thanks in advance

[DJ Omnimaga]

Yeah I simply went to the attachment list personally, as I couldn't find it through posts. And yeah admins can find a specific attachment post, but it's one single list for the entire forum, so your post would be buried in the list behind about 1000-2000 posts, most likely.

Anyway I'm sorry for the personal attacks if I made any. I guess I was kinda frustrated at the last part of the post then later how this matter was brought up on another IRC channel (I do not know the intention behind this) that had nothing to do with Omni, and when I am angry I tend to say things I would not say normally. You are free to rate down my posts if they contain any.

[Lionel Debroux]

Anyway I'm sorry for the personal attacks if I made any. I guess I was kinda frustrated at the last part of the post then later how this matter was brought up on another IRC channel (I do not know the intention behind this) that had nothing to do with Omni, and when I am angry I tend to say things I would not say normally. You are free to rate down my posts if they contain any.

ACK. Let's move forward together then

I'm not sure I'm in a position where down-rating your posts wouldn't be considered rude
But yeah, for example, "but so far you contributed no code for a better RSA key factorer program" and "If people here had the experience to write a better factoring/whatever algorithm in the way Lionel suggested and in ASM, I am sure it would've been done long ago", and "and more like you are offering your help", as replies to a message that contains an explicit mention (even though no direct link) of such code of mine (though as I also mentioned, I did not fully write it myself), was very rude