arthur@arthur-PC:~$ mono Nspire*.exe
1024 bit TI-Nspire boot2 RSA Key:
0xc3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d
0x3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b
0xbcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c
0xdf80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7
Unhandled Exception: System.ComponentModel.Win32Exception: Access denied
at System.Diagnostics.Process.set_PriorityClass (ProcessPriorityClass value) [0x00000] in <filename unknown>:0
at (wrapper remoting-invoke-with-check) System.Diagnostics.Process:set_PriorityClass (System.Diagnostics.ProcessPriorityClass)
at NspireKeyFactorer.Program.Main (System.String[] args) [0x00000] in <filename unknown>:0
arthur@arthur-PC:~$
I'll give 6000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000 a try. I hope this doesn't take half a year to run.
3000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
3000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002
sudo apt-get update mono
;)
Sounds good :P if you really want to, this program only sets its priority to High, you can manually set it to realtime from the task manager ;)I will do that. And what if we made this a competition to see who can test the most keys in a month?
BTW after 9 it's A right?
I get the exact same on linux!!! :PSir just ninja'd you with the answer to life, the universe, and everything. :P
512 bits are 128 hex numbers, usually.
And DT is right, if the first bit should be 1, so the number must be higher than 8000...?
(can now use any custom mscorlib)
julien@amy:~/NspireKeyFactorer$ echo -n "9"; for i in `seq 1 127`; do echo -n "0"; done; echo;
90000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
julien@amy:~/NspireKeyFactorer$ mono NspireKeyFactorerv1-2.exe
1024 bit TI-Nspire boot2 RSA Key:
0xc3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d
0x3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b
0xbcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c
0xdf80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7
Ready to begin. Press 1 to start at the minimum 512-bit value,
or anything else to specify a number.
Please specify which number to begin from (in hexadecimal):
90000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Invalid 512-bit number.
do
rannum = random() // generate random 512 bit number or greater
num = gcd(rannum,n)
while(num == 1 or num == n) // break from loop if rannum a multiple of one of the primes ?
print "Great !!!, factor found ", num
Then it would finish when it found a random number thats a multiple of one of its primes.I'm working on a server now... what do you guys suppose that would be a good range length to begin with? I think a whole 512-bit range is a bit too much.Is it feasible to complete Sir's current range. 100000000...
Um, people, remember ( http://ourl.ca/6418/129294 and other posts of mine): factoring a 1024-bit RSA key, using the best known algorithm, is a task more than three orders of magnitude harder than the state of the art (using unpublished algorithm implementations - the open source implementations aren't at that level yet, by a significant margin).Lionel Debroux, I think you need to tone down on the harshness. If you post a post like the above again, you'll be banned. You are not allowed to say anything negative against other people project unless you can contribute something better to it. Also saying facepalm to people is against the forum rules because it is rude and intended to make them feel like they have lower intelligence, which is not the case, and telling them they fail at something. There are nicer ways to say things. I decided to rate down your post.
IOW, a problem that only very few persons in the entire world would have an idea how to tackle, let alone have the resources to run to completion - we're talking about dozens of thousands of cores for the sieving phase, and some pretty odd clusters and implementations for the post-processing phase...
As I wrote, some TF'ing can be done, although very extremely unlikely to succeed. It's even OK for you to make some software similar in spirit to the PRPNet/ECMNet server+client (that's where I'd start looking, if I wanted to make client+server software for RSA TF'ing).
So I'm not criticizing the idea itself. But if you're into TF'ing, then please, don't make an inferior independent reimplementation of a working wheel that was created months ago, on this very forum...
Namely, a C# TF'ing program with primality checking is a two-fold waste of CPU power - and a significant one at that, judging by the very low rate of progress indicated in various posts here (IIUC DJ's post, 3K divisions per hour... ouch !! Even 3M/hour would be bad):
* using C#, Java or any other language of the same class, for such kinds of very heavy number computation, is a cardinal sin. Even AOT compilation of those languages doesn't let one get down to the performance of C/C++ directly calling into highly optimized ASM-based libraries;
* the computational cost of primality-testing the numbers is extremely prohibitive, as shown by myself when optimizing the C program started by Tribal. Dividing mindlessly N, without any form of primality testing for P, makes the program much faster. And it can even be made slightly faster by adding several trial divisions to weed out the most obvious non-prime P. Check the post I linked to above in this post, and the topic that it links to.
And what's more, P or Q are very unlikely to be near enough from 0xxxxx00<many zeros>00 to be vulnerable to TF. Look at the hexadecimal representation of the factors for the TI-Z80 and TI-68k RSA keys. Choosing P and Q for making a good RSA key N=P*Q is a complicated process, which must (in the RFC sense) contain checks to ensure that P and Q are not too easy to find by indirect methods: strong primality testing/proving (APRT-CLE / ECPP / AKS), for P and Q; P-1, P+1, Q-1, Q+1 having at least one very large prime factor (i.e. P and Q are dubbed "strong primes"); and more.
I'm no cryptographer, and I don't know how any of the efficient integer factoring algorithms works. But after feeding the RSALS grid with more than 200 integers considered large for individuals or small groups of individuals, attending the serious sections of MersenneForum for one year and a half, and having some data about the harder factorizations done by the NFS@Home grid (which are still significantly easier than the factorization of a 768-bit RSA key), I think I have a better idea about the difficulty of factoring a 1024-bit RSA key, and the most efficient methods to achieve this aim, than all of you do ;)
TL;DR: facepalm. You guys fail at implementing a decent program for the task of factoring a RSA key, fail at using it, and as a result, you're wasting the vast majority of the CPU time you're devoting to it. Heaven forbid anyone notify MersenneForum, especially personalities such as Professor Robert Silverman, of this topic...
@Ruler you can take that one step further, and eliminate roughly 69% of the numbers.We could go even farther by using the sieve of eratosthenes to calculate a large range of primes first, then test only those primes.
@Ruler you can take that one step further, and eliminate roughly 69% of the numbers.Can we just eliminate 70% of the numbers? Or how about 99%? Anything that lowers the numbers to check is a good algorithm to pursue. Let's see, if we stored 2^512 bits in memory (2^509 bytes) for each number 0-2^512, we could then reset each bit when we disregarded that number by some algorithm. Interesting thought memory wise, no?
My test count is now up to 270,000Daaaaamn
Because that is extremely difficult.That and the networking overhead, server that maintains it, etc. would all slow it down more than our individual efforts.
oh.. yeah I didnt think about that aspect of that.. well it is a neat concept nonetheless. Once I build my computer, I will run this thing at ~4.8 GHz at most with 4 cores. BTW you should make this utilize quad core cpu's that would be a nice feature :DHe could just create a linux live CD. That could work pretty well.
Or maybe we could write a bootable mini os that will only compute this task and run nothing else on it (no windows explorer, or task bar, or any windows services). Basically to utilize every single ounce of cpu power there is.
I don't know if this has already been asked, but why not write it in x86 asm or C? They are faster than C#, and they are also more compatible with other operating systems. Other than that, very nice, although I don't think the key will be factored soon. :/It will be. calc84 is working on a C/inline ASM version as we speak. ;)
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 ;)
by pointing the well-known, common sense fact that C#, and other languagesIf 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.
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 ;)
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 ;)
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 ;)
Just how many times do I have to say that I don't expect the brute force method to work? I know it won't work. But it is possible to happen, and it's better than doing nothing.^ this