I don't see what this has to do with '(n-1)/2 = sumdigits((n+1)^2)' though.



iblis,
Nothing at all. I was just answering Svin's inquiry. Ratch
Posted on 2002-11-22 13:34:15 by Ratch

How do you call Minor Theorem?
Found it!
http://www.spd.dcu.ie/johnbcos/download/Public%20and%20other%20lectures/Fermat's%20little%20theorem/Flt4.html

:grin:

(Prime) p = 1 (mod 4) = a^2 + b^2

Let (p) be any prime, and (a) be any integer not divisible by (p), then a^(p-1) leaves remainder 1 on division by (p).

I did not know this was Fermat, and have had great fun reading his biographies on the web.
Posted on 2002-11-22 19:38:07 by bitRAKE
bitRake,
have you found solution to
if there is number = (n+1)^2
where sum of digits = n(n-1)/2
?
Posted on 2002-11-22 21:59:23 by The Svin
n = 2

(n+1)^2 = 9

Sum of digits (base 3) = 1

n(n-1)/2 = 1

------------------------------------------

n = 2

(n+1)^2 = 9

Sum of digits (base 9) = 1

n(n-1)/2 = 1


Thank you :)
Posted on 2002-11-22 23:19:03 by bitRAKE
Dudes,

Yes, but the 5 bytes code? :grin:

That would be interesting to see too. ;)
Posted on 2002-11-23 00:48:29 by Maverick
yea, show us the * code :D

please :)
Posted on 2002-11-23 16:37:52 by nyook
I'm saying it again (hopefully for the last time):
It's for you to find the answer or prove that there is no answer (that it is impossible).
It's not reference book or cook recepies, it's training tutorials.
The way to find out answer here is more important than the answer itself.
And asking me for the answer is not the way :)
If you are getting string feeling that there is no answer, you shuld prove it:
There are two obvious ways to do it.
1. Analitic approach:
You need to do yourself job kinda I do it the info part of the tutorials:
Collect info that can be used in solving the task.
Structurize it:
Ways to set bits in EAX, AX
Ways to use PF
Ways to overlap code
etc.
And show that there are no ways :)
2. Brute force method:
Write brute force also that would check 2^48 possible values, if
there is (or are) some that do the job.
Use SEH to pass by exeption of unkown code
and code modifining method (make code section ERW)
to iterate through those values.

I say it again: I don't belive ANY book could teach anything,
book only can be used in learning when you use it for practical things:
creating and observing examples, doing exersizes and using ideas from it real
practice.
In other word doing something with your hands and brain, using the book as
helper, not solver.
Posted on 2002-11-24 00:03:52 by The Svin
Svin, remember you said, "Oh It's no problem, I could admit anything. I've proved it before."

"I've proved it before."


So you obviously know the answer, right? You've either proved it to be impossible or proved it to be possible. Either way, you know.

I don't know how many people believe you, but perhaps as a sign of good faith, you could write down either the 'disproof' or the 5 byte solution in a .txt file and zip it in a password-protected .zip file and upload it now. Kind of like a 'sealed envelope' ;)

Then when one of us proves/disproves it, you can give us the password to the .zip file and we can check it out. ...Or you could just admit you don't know the answer and join us all in the search for it. ;)



Anybody else like this idea? :grin:
Posted on 2002-11-24 00:52:10 by iblis
I have faith in Svin and we gain either way. Like Svin stated we must do the work if we are to learn - it is the process which is important. If Svin has not done the work then he would only gain an answer and not the experience of the process - he is not that man. Although, I can see your point iblis - I do not see why it is important that Svin have the answer. Svin is trying to provoke discussion to deepen our understanding - not unlike Fermat! :) Can you see how this problem is not about Svin - he is a selfless man. He is not saying, "I have completed this great puzzle - see if you are great, too!" OTOH, if Svin did post an encrypted answer to the problem then the challenge would be more concret to some. iblis already has outline a good approach to eliminating most possiblities.
Posted on 2002-11-24 01:17:20 by bitRAKE
Let us start analytic part of job:
Enamurate all thinkable possibilities to
set bits in eax, ax.
Do it in opcodes.
Spell size of it, and comments that you think might relate to the task.
Posted on 2002-11-24 03:36:48 by The Svin
Hi The Svin, you wrote:
I'm saying it again (hopefully for the last time):
It's for you to find the answer or prove that there is no answer (that it is impossible).
It's not reference book or cook recepies, it's training tutorials.
The way to find out answer here is more important than the answer itself.
And asking me for the answer is not the way :)
If you are getting string feeling that there is no answer, you shuld prove it:
There are two obvious ways to do it.
1. Analitic approach:
You need to do yourself job kinda I do it the info part of the tutorials:
Collect info that can be used in solving the task.
Structurize it:
Ways to set bits in EAX, AX
Ways to use PF
Ways to overlap code
etc.
Theories have been proven wrong.. expecially those that make assumptions like "the only ways to solve this problem fall into 3 cathegories: Setting bits in EAX, AX; Overlapping code, ".. so I'm afraid the only proof that could be considered 100.0% reliable is brute forcing it. While it would be certainly doable, not everybody here has the (time) resources to do it.. that's why some would like to know at least if it's possible in 5 bytes, in order to invest their time more into finding the solution (assuming there is one). Take it only as an advice.. the thread is yours and I respect your choices. :alright:

About brute forcing, I'd make an x86 emulator (we can make one in some days :grin: ), start/run a 40 bit counter, disassemble the 5 bytes sequence and rule it out immediately if it falls beyond the 5 bytes (e.g. an immediate value crosses the 5 bytes boundary), and apply further "100% sure" filters, as the CALL and long-JMP instructions, the MSR ones, etc.. the better the filter, the less real tests one has to perform in the emulator.
Hey, now that I think of it, if the development time for this tool wouldn't be justified for this single challenge, it would for many other projects. I'd invest some time on it if it wasn't that its true usefulness would be in finding shortest solution for a certain code sequence, and not the fastest one (something I'm certainly much more interested).

I say it again: I don't belive ANY book could teach anything,
book only can be used in learning when you use it for practical things:
creating and observing examples, doing exersizes and using ideas from it real
practice.
In other word doing something with your hands and brain, using the book as
helper, not solver.
I fully agree.. but you forgot to put "time" into the equation. ;)
Posted on 2002-11-24 03:51:17 by Maverick

About brute forcing, I'd make an x86 emulator.
Maverick, that is the slow method! Why bother with weeding out illegal instructions? Why bother with ensuring only five bytes? These features are built into the CPU. Even if he cache was turned off (to test SMC code) it would be faster than an emulator. It could be brute forced in less than a day. The code would be under 4k (maybe ;) - not pretty).
Posted on 2002-11-24 04:19:54 by bitRAKE
:)
OK let us then put rating of the problem as 50
according to D.Knuth rating table.
Who read D.Knuth can understand what I mean.
Anyway I'm not going to say "I knew it!!!"
if I see someone solution.
Let the one who'll find it feel himself as absolute winner.
For me it is very important that the man could feel himself as a winner.
Better than anyone in solution, including me :)
And that solution to be searching for and process to be provoken by reader inner intention.

For now I'm working on training software for next tutors.
Posted on 2002-11-24 04:26:26 by The Svin

Maverick, that is the slow method! Why bother with weeding out illegal instructions? Why bother with ensuring only five bytes? These features are built into the CPU. Even if he cache was turned off (to test SMC code) it would be faster than an emulator. It could be brute forced in less than a day. The code would be under 4k (maybe ;) - not pretty).
Ricky, I'm afraid of exception costs under Win32, they may be very big. :rolleyes:
Posted on 2002-11-24 04:27:58 by Maverick
Who said Win32? Just a couple sectors on a floppy = hex bytes on screen...

Posted on 2002-11-24 04:39:04 by bitRAKE
Cool :alright:

But one more problems meets my mind: how do you handle boundaries? (e.g. for branch or JMP or CALL). You could easily do it on a per-page basis, i.e. behind the 5 bytes it's easy, but after ( and <4096 ) it may be difficult.
Posted on 2002-11-24 04:51:51 by Maverick
I offer for a change another task that easier.
I just want to know if people other than iblis and bitRake
understood what was tut #3 about.
So I ask iblis and bitRake don't publish their answers
to the following task for a while to see how others can
solve it (you can of course solve it but keep silence for a while).
Task simular to previous but with one exeption:
It is unknown what value is in eax but known that sign bit in eax = 1
(bit 31)
Now the same task:
set all bits in eax to 1 if PF=1
if PF=0 set only low 16 bits in eax (keep upper 16 bits untauched if PF=0)
Posted on 2002-11-24 08:12:12 by The Svin
Hello, bitRAKE.

Ratch, I don't think it requires brute force for this problem - my ASM skills are better than my math. :) I will try to work through the math though - I need the practice. Good to see another person join in the discussion.

Brute force is unique solution. Realy this task must be written so:
(n+1)^2=sum(Di*B^i)
(n-1)/2=sum(Di),
where i - count of digit; Di - digits; B - base
Here unknowns very much = digit capacity(Di) + 1(n) + 1(B).
Math can found solution only for two unknowns (apply simplification):
(n+1)^2=Dx*B^x
(n-1)/2=Dx,
where x - one of digits position.
But is other task. For initial B=2, Dx=1 => x=4, n=3.

Brute force can be speed up, if use singularity of equations.
Ex. you code would be double speed: start ESI from 1 and step 2, because n always odd.
---
Best regards,
Nexo.
Posted on 2002-11-24 10:34:07 by Nexo

But one more problems meets my mind: how do you handle boundaries? (e.g. for branch or JMP or CALL). You could easily do it on a per-page basis, i.e. behind the 5 bytes it's easy, but after ( and <4096 ) it may be difficult.
I see two methods: fill the page with int3 instructions, or singe-step on branches tracing. Both can be used, or the later could be turned off for faster execution.
Posted on 2002-11-24 10:44:18 by bitRAKE

Brute force can be speed up, if use singularity of equations.
Ex. you code would be double speed: start ESI from 1 and step 2, because n always odd.
Good observation!
Posted on 2002-11-24 10:46:36 by bitRAKE