yashsingh1/xdaforums huggingface dataset:
[Motorola Milestone Android Development] Ming-Z:
Certainly a stupid question about the Work Units, but did they are chosen randomly from the total keyspace ?

Because if I correctly understood the way this projects runs, the bruteforce method to crack this key is to test every single key till we match the correct one.

According to my calculations, a 1024 bit key includes something like a range of 1,8 x10³⁰⁸ different possibility.

It seem that a single BOINC Work Unit is a pack of 10¹¹ single keys tested.

So, please, say me we are testing randomly and not from key #1 to key #1,8 x10³⁰⁸
[Motorola Milestone Android Development] pontomedon:
No, the workunits are not created randomly, but in order from the first to the last.

Don't get confused by the work unit names, they consist of a unix timestamp (when the work generator was started) and an incrementing number. This is necessary for the work unit names to be gobally unique, even if i restart the work generator (which happens from time to time, e.g. when i changed the work unit size)
[Motorola Milestone Android Development] djefkbefke:
So if I get this right, we won't ever find this key if it somehow happens to be in one of the last possibile workunits :confused:

I think we should all put in some money and hire a professional Opencl-capable programmer (because there are people who do have an ATI card ;)) to

assist

pontomedon in developing a nice, fast GPU application? :D:D

And also a second project which processes workunits from the last possible one to the first, so we can eventually meet in the middle? :D

No pun intended and for the record, I'm not being sarcastic :D
[Motorola Milestone Android Development] pontomedon:
i thought about the order of the workunits for a long time, but the probability always stays the same, because possible solutions (prime numbers) are more or less uniformly distributed over the whole interval.. if we split forces and start from the back as well, we'll have half the speed on both ends, so it won't have any benefits, and i would have to run two separate work generators, which puts a higher cpu load on the server, and means more effort from me.

I decided to use the simplest possible approach, because it uses the least resources (cpu and memory for the work unit generator), the way i do it now, i only have to remember the last created work unit when creating new ones, if i created them randomly, i would have had to remember every single created work unit (which would sooner or later fill every harddisk i have, and it would also be much slower).
[Motorola Milestone Android Development] be0ne:
ok, let's crack this thing

My good old Milestone is out of warranty now... I whish I could flash any new trendy rom with the latest kernel (even if I already use FroyoMod and CM builds).

Anyway, got it installed yesterday and I hope the humble Core i5 of my computer will help. 1024 bit RSA is a tough encryption, bruteforce is bruteforce... let's see where we get with this thing !
[Motorola Milestone Android Development] MystikIncarnate:
I'm here! I'll have to do some additional work to get my *nix box working on this, but I'll add this to my main systems and windows systems ASAP.

2x64 (C2D) and at least one x86 system adding to the pool...

Edit: I tried to add both my servers and two desktops to the mix, the desktops went fine, one server went fine, but the other server is a domain controller, and the boinc installer threw the error that it couldn't create the boinc_admins group (probably because it's trying to add them to local groups, rather than the domain)... that server is always on, doing nearly nothing right now, and it's x64, but I can't change the config to not be a domain server at this time, so the boinc install consistently fails.

I'll try again later... if anyone finds any information regarding this issue, please post links. I want to get all four systems working on this.
[Motorola Milestone Android Development] zankyw:
This

and this

is what really encourages me to keep going :D
[Motorola Milestone Android Development] drleospaceman:
edit - delete
[Motorola Milestone Android Development] thenotdone:
Joining team Canada RSA with my quad-core pc :)

Too bad theres no way to use my PS3 as well...
[Motorola Milestone Android Development] hotplainrice:
Just finished reading the whole thread.

1. Is the code parallelised for multicore systems?

Its because I can dedicate systems to this but there is no point dedicating a quad core sys if only a thread runs.

2. Is it better to have a system with 8 cores running or 8 single core systems?
[Motorola Milestone Android Development] Ming-Z:
1. Yes, each core is used to calculate a dedicated Work Unit, so if you have 8 cores on your machine you'll be calculating 8 Work Units at the same time.

2. The better way (considering energy consumption) is to run the much cores as possible on the less systems as possible.
[Motorola Milestone Android Development] Ming-Z:
Thanks for explainations, I understood the physical problematic about distributing randomly WUs.

That's no luck, because the best way to deal with random stuff is to act randomly.

I guess the best optimisation this project could receive should come from the way the WUs are distributed for calculation. We're dealing with too high numbers to think in term of pure speed or computing power. We need some randomity or to multiply start points in the distribution of W.U. to really add some luck in the deal.

The number of people involved in this project seems to grow day by day. Maybe some of us could help supplying ressources for work generation ?
[Motorola Milestone Android Development] pontomedon:
If you recall some probability theory, you'll see that there's really no benefit of randomization. The probability of finding the key in a decent amout of time will always stay the same.
[Motorola Milestone Android Development] Ming-Z:
Absolutely right, but I'm speaking of luck ;')
[Motorola Milestone Android Development] pontomedon:
which won't change either. if we start randomization we could just as well miss the correct result we would've found without randomization.

works in both directions :)
[Motorola Milestone Android Development] WarZman:
Joined the club. With for now 2 computers. Have to fin d a way to instal boinc on server 2008 r2 with dc on it. After I figured that one out I there will be 3 of my computers calculating.

I already asked my boss to install it on al the windows servers we own but its a little to risky.
[Motorola Milestone Android Development] mazhas74:
Hi,

Do you have any number in percentage how far p(or q) value from sqrt(n)? If you would post the p (or q) value from the latest batch it is relatively easy to calculate how far away it is from sqrt(n). If you divide delta=p*100/sqrt(n). That would give a clue how fast or slow you are performing and how much time is left.

I've noticed by generating private key by using openssl that usually smaller factor (p) is between 86-99,9% of the size of sqrt (n). Because you have decided to go up then bigger factor should be between 100,001-114% of the sqrt(n) value.

Other observartions (if you determined not to use classical factoring methods such as QS or GNFS):

a)If you would go down <sqrt(n) then numbers would be smaller therefore potentially faster operations. It is still possible to revert to the opposite direction because p=n/q but it's up to you of course because needs changing code and gain would be minimal.

b) It is not very wise to do division and then throw away the result right after the operation. You should be looking for some sort of sieve to do mod operation on numbers with higher probability than just odd numbers:

You could use idea from w w w .devx .c om /vb2themax /Tip/ 19051 to throw away some of the odd numbers

c) If you draw a function of y=n mod x for some small n you would see "waves" and you will find 2 y values that y=0 at the bottom of one of the waves (if n is composite of 2 primes). For 1024 bit n wave period is =500 at 99,9%, =16 at 97% and =3 at 86%. The problem is that wave period is changing slightly but can be constant for long ranges for such big numbers +-1.

I also thought that it would be possible to check last bits of wave bottom value pairs (p<sqrt(n) and q>sqrt(n) - they exist in both directions) without even actual divide operation and do some ranges by using usual integer (or unsigned long) data type because we would care about last digits only). I cannot prove but when I played with small n's it seems that the same count of waves exist between p and sqrt(n) and between q and sqrt(n).

d) Another idea which is quite interesting: w w w .mathpages .c om /home /kmath222 .h tm
[Motorola Milestone Android Development] dcarr622:
What's up with transitioner Not Running and MilestoneRSA_bitwise_validator Not Running? Should this be cause for concern?
[Motorola Milestone Android Development] Menelkir:
Joined. One more windows 64bit helping.
[Motorola Milestone Android Development] dcarr622:
NVM seems to be all green now... weird.
[Motorola Milestone Android Development] pontomedon:
was down for a few hours, had to backup/restore the whole db, but fortunately no data was lost (didn't even have to restore an old backup, but was able to do a current and restore it immediately after). everything up and running again.
[Motorola Milestone Android Development] Babis_ECE:
Just joined with my Ubuntu 10.10 64bit, Core 2 Duo laptop. :)
[Motorola Milestone Android Development] Ming-Z:
I read the whole topic and found very intersting infos about the way we are proceding to find the key. Everything is more clear for me now, thanks !

You explained that the worker tests only odd numbers in order to restrict calculations to some possible prime numbers. But does numbers ending by the digit 5 are included in those tested odd numbers ?

Because if I don't make any mistake, there is no other prime numbers that 5 ending by the digit 5. The fact to avoid to calculate numbers ending by 5 could it result in a gain of speed ?
[Motorola Milestone Android Development] ouilsen:
I may be wrong about this.

If you think about it, checking whether a number can be divided by 5 is easy to do in the decimal system, since it is base 10=2*5.

A computer however uses the binary system. So by _looking_ at the last bit, you can only check whether it can be divided by 2. Checking the number 5=101 is harder.

Your suggestion requires to convert the binary number inside the computer memory to a decimal number, which by itself requires some computational step.

It is very interesting though, since one could of course invent a computer using numbers base x where x is very large. Preferably 2*3*4*5... The problem then is, I guess, that 'looking' and recognizing a number will take longer and longer.
[Motorola Milestone Android Development] Ming-Z:
I was expecting something about extra computational step in order to check this...

Thanks for your explaination.
[Motorola Milestone Android Development] Ming-Z:
Agree with that. Going down from sqrt(n) will result in something like 5,7 x10^153 [ sqrt(n)/2 ] numbers to check. Going up is more something like 6,5 x10^307 [ (n-sqrt(n))/2 ]

Reverse the machine captain !

I also played with thoses "waves" (sawtooth shape). It seemed for me they were ruled by a period f=n/x with sqrt(n)>x>1
[Motorola Milestone Android Development] afadel:
What gets in my nerves is why the heck they locked it?? It's not like they have the perfect kernel and I'm shure they could benefit from the community tweaks on their releases.
[Motorola Milestone Android Development] PoLiThS:
Perfect kernel? lol. The opposite maybe...

What makes me feel strange is why they bothered developing 2 different variants of the same device... Milestone and Droid.. Droids have unlocked bootloader because of the us laws and I feel sure about it
[Motorola Milestone Android Development] grigorbg:
Btw Motorola now is not a green company :-)

All this CPU power (watts) that calculating the stupid key is because Motorola decision..
[Motorola Milestone Android Development] ozzmanj1:
Okay I emailed Engadget (Editor Chief) and kindly informed him of the work going on here, and posted him the link. I did give him the background as to why we are doing this. Also thank you everyone for all your work. I myself am a disgruntled Milestone owner. I hope this works, then we can throw this into Motorolas face. Also I noticed all the negative flack the Facebook page was getting. Now apparently you can no longer post comments on the Milestones FB page. HA! I find that funny, and yet so annoying.
[Motorola Milestone Android Development] zankyw:
Would be great to get this in Engadget, but I don't think it'll get much attention considering the CES madness happening these days. :)
[Motorola Milestone Android Development] DannyDroid:
Nothing to due with US law as the Droid is the *only* Motorola that doesn't have a locked bootloader.

No reason was given but it was most likely something to do with Google as this was a "With Google" phone.
[Motorola Milestone Android Development] mxzas:
Engadget is posting RSS feeds like crazy regarding to CES.
[Motorola Milestone Android Development] mazhas74:
Pontomedon,

Can you post current value of q from the last work unit?

N.P. I found one from my work unit data. To have a clue where we are I can say that we are still at the start position:

n=130302296876495664949661851680712011323312218834692385409623477008770865634659674156795804984537277912018798333263614293465141543417786692641368992984327637616442187669331580699115569820799572488140940906656454027164582729057745051164346395037158084882727830713343954973996507744959096964190716798991681022591

p=11415003148334899384013279559163006252503622953398488105987646973643900410666035949132818535247549956820194598606112687931423964886057878156176826716579120

sqrt(n)=11415003148334899384013279559163006252503622953398488105987646973643900410666035949132818535247549956820194598606112687931423964886057878152536926716579120

p*100/sqrt(n)=100.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000031886982%

I've mentioned before that p value usually is between 100.001-114%
[Motorola Milestone Android Development] etoy:
i'm curious if there's a way to know how much progress has been done for now? i mean,some kind of a percentage between 0 and 100 that shows how many combinations have been already tested...just to have the feeling that the work does proceed (even if slowly) :)
[Motorola Milestone Android Development] evolucja:
It's about:

0,00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001%.

for now.
[Motorola Milestone Android Development] pontomedon:
i don't think those are enough zeros, but yes, more or less :)
[Motorola Milestone Android Development] etoy:
haha,thanks! :)
[Motorola Milestone Android Development] Ming-Z:
Pontomedon,

What about suggestions made in post #224 regarding the way to check P by decreasing it from sqrt(N) to 1 ?
[Motorola Milestone Android Development] pontomedon:
I'm planning to do that, but i'll have to change the work generator a bit, and didn't have the time to do that yet. expect the change in a few days.
[Motorola Milestone Android Development] sb07:
My Quad-Core join it!
[Motorola Milestone Android Development] drowne:
I've just joined the group. i hope to see the GPU support as soon as possible.

For the Milkyway project it changed work time like this:

CPU: 10hr/work unit

GPU: 3 minutes / work unit
[Motorola Milestone Android Development] zankyw:
That's an impressive 200x improvement!

What makes GPUs that much faster in this kind of calculation?
[Motorola Milestone Android Development] butcher211:
I'm going to help you too! I start tomorrow in the morning with it.

My Phenom II @4x 3,4 GHz needs new tasks! :P

SO F**K SETI@home! :P
[Motorola Milestone Android Development] zwierzak:
It is connected with matrix calculation, no GPU you can calculate 32 values at the same time. So you get 32 operations instead of 1. There are also other optimizations.
[Motorola Milestone Android Development] Ming-Z:
Is this your computer ?

How is it possible to have such a blazing fast calculation time ?

Worker does not seems to be the official one... I'm wondering about this user...
[Motorola Milestone Android Development] evolucja:
It's computer of member of Polish national team. He has modyfied the worker. Currently I don't know anything more. I contacted him by email.
[Motorola Milestone Android Development] 5nickers:
we have to get the worker of this polish guy. the speed is awesome. i think he already implemented gpu support!!!
[Motorola Milestone Android Development] dcarr622:
Fascinating, his speeds are incredible! OP can you comment?
[Motorola Milestone Android Development] cantIntoCode:
Wish you guys the best of luck! Hopefully not too long now before the key is cracked :)
[Motorola Milestone Android Development] consolation:
Yep, only a few orbits around the galaxy core and you'll be done.
[Motorola Milestone Android Development] evolucja:
I think he doesn't know what's going on....
[Motorola Milestone Android Development] k1l:
on irc he told, that boinc should not allow to fiddle at the worker. so it seems to be that there is some obscure going on.
[Motorola Milestone Android Development] thesparxinc:
the projects current GigaFLOPs raised in last ~24hours from about 3 gflops to over 7 gflops.
[Motorola Milestone Android Development] evolucja:
It's not looking okay.
[Motorola Milestone Android Development] sandimann:
it raised from 3 _TERA_flops to over 7 _TERA_flops ;)

because of the polish guys we can cancel our project, i guess. If they are cheating they are not calculating anything. But: they are requesting new tasks again and again. All these tasks are lost. And if the key lies in one of these units, we will never get our key at all.
[Motorola Milestone Android Development] GieltjE:
Tasks have a due date, so if they are not submitted they will be re-released.
[Motorola Milestone Android Development] The Solutor:
Polish guy or not, seem that ironically the project needs an electronically signed worker to avoid cheats.

What if someone (possibly @motorola) will start to "poison" the project with a cheating worker ?
[Motorola Milestone Android Development] Ming-Z:
Does anyone is in touch with this Polish Guys and able to have some infos on what they are actually doing with their custom worker ?
[Motorola Milestone Android Development] evolucja:
@Ming-Z

Sure. I've just received an answer from sesef, a member of Polish national team.
[Motorola Milestone Android Development] sandimann:
If this is true and they are not cheating but they have a worker that is lots and lots faster, then we would need a server farm to host the project :D But I dont believe anyhing until they share there work with pontomedon.
[Motorola Milestone Android Development] evolucja:
We wouldn't. We'd have just to increase the wrok unit size.
[Motorola Milestone Android Development] djefkbefke:
would be nice to have this worker.. we might actually get somewhere at those speeds :D

imagine that worker combined with OpenCL (which is based on C, so there should be somebody capable of programming it?) If only I knew C i'd digg into it myself :D
[Motorola Milestone Android Development] k1l:
if someone is familiar to all this boinc and coding stuff and could help pontomedon/poseidon i think there is a good chance to get the speedboost for evereyone. (maybe someone gets cuda running). unfortunately he has no spare time at the moment for this project (and it would take even longer for me to get those skills than to run it as it is)

if someone has some server capaticies left and could e.g. host some mysql db the project downtimes would decrease.
[Motorola Milestone Android Development] evolucja:
@MuF123

Polish national team is one of the most respected BOINC team. Look at global BOINC statistics... If you have any questions you can contact them. I already did and they explianed me what are they doing.

MOD EDIT: Less of the abusive language please...
[Motorola Milestone Android Development] djefkbefke:
Yeah, give them some credit.. maybe they implemented some code to filter out useless calculations or whatever :confused:

I once tested an improved version of the worker for x64 linux (posted some pages ago by zwierzak) which was indeed faster and guess what.. he happens to be Polish, show some respect please ;)
[Motorola Milestone Android Development] djefkbefke:
yeah, I do agree with you on that one.. they are testing their bleeding-edge builds on a small scale within the group, but they could release the code to an improved (

stable

) version to pontomedon ;)

I think perhaps it's because of the fact pontomedon doesn't approve of custom builds (which is from his point of view rather logical :D) .. we might however doublecheck some random results of this superworker to make sure there's no cheating involved, but this means extra work for pontomedon.. let's just wait and see ;)
[Motorola Milestone Android Development] jackeh070:
Dear MuF123, you of course noticed that server often hits 0 (or a few) tasks ready to send, right? It wouldn't be able to prepare all the tasks in time, unless the workunit would be much bigger.

Stop being a jerk, give them a day or two to consult the thing with our OP and we will see. It's better then having to apologize later on :D
[Motorola Milestone Android Development] evolucja:
I've just got another answer. I totally agree with him.
[Motorola Milestone Android Development] DooMMeeR:
1. release the code of the worker

2. create new tasks for the new worker

3. push the new worker with the new tasks to the cients

if the new tasks get pushed to old workers they will FAIL to complete them because of the endless calc time :P

I cannot see how those extreme improves work out, but I am willing to see some ASM with extensove SSE or other IPU usage that is getting that results

not sharing the worker and it's code with the community is just wrong anyways and crediting someone for a somewhat unfair or private race is not what I support

but credit for trials or just contribution after all is fine for me and I will credit those improving the client :P

GGPU-Calc with OpenCL might even improve this further :P
[Motorola Milestone Android Development] Jockson:
I don't even have the Milestone but I'm considering one so you can count me in ;)
[Motorola Milestone Android Development] the_scotsman:
Guys, I've cleaned up a few comments...please keep the thread on topic. Anyone else starts mouthing off, there'll be infractions handed out :)
[Motorola Milestone Android Development] raptor1977:
Statement about optimization for MilestoneRSA

htt p://poseidon.shacknet.nu:8080/MilestoneRSA/forum_thread.php?id=14
[Motorola Milestone Android Development] jackeh070:
Work generator is down;

The statement makes sense, and I really hope that OP will consider it (as long as he is still interested in the project, of course).
[Motorola Milestone Android Development] zankyw:
Guys, it's Sunday, be patient and relax! ;)
[Motorola Milestone Android Development] amossam:
You have my phenom x4 @3GHz, working nothing 24/7 !!!

:D hope we can get some clarifications with these worker tweak!!

Sent from my Milestone
[Motorola Milestone Android Development] dcarr622:
http://poseidon.shacknet.nu:8080/MilestoneRSA/forum_thread.php?id=14

reposted for the ultra-lazy

really hoping the OP can come back and clarify things. If these guys really are right, this could greatly improve our chances. I'm an optimist, and I'm hoping they are right :) OP was online today so hopefully he didn't abandon us :)
[Motorola Milestone Android Development] nabuhonodozor:
I cant send my completed WU since 2 days. Server is down?
[Motorola Milestone Android Development] MystikIncarnate:
I believe it's down, since if you try to go to the main url from the first post, it returns with not found or not responding...

the OP will have to check on the status of the server. Not surprising it's been down, but I've only been working on my WU's for a few hours? so maybe it's intermittent?

just keep boinc running, it'll iron itself out.