- Milton Brown wrote:
>

No they are not. When he uses the ^ operator, he means the xor (exclusive

> Sorry, what is the purpose of n1 = a1 ^ 1 and a1 = n1 ^ 1 ?

> Aren't these just n1 = a1 and a1 = n1 ?

or) operator. If you don't know about the xor operator, here's a quick

tut:

0^0 = 0

0^1 = 1

1^0 = 1

1^1 = 0

So, what n1 = a1 ^ 1 basically means is if a1 is 0 then n1 is 1, and vice

versa. HTH.

-David C.

>

> It would be helpful to explain these, or have your mathematics

> thought out more before posting.

>

> Thanks.

>

> Milton L. Brown - -----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1

Justin asked me for a real life example of how this technique

can be used to find factors, so at the risk of boring everyone

else, I thought I'd post it here on the forum. Here is a sample

Maple code snippet ('#' begins a comment) that illustrates the

problem:

n:= [0,0,1,1,1,1]: # factor binary 001111 = decimal 15 = 3*5

c1:=a1*b1:

c2:=(a2+a1*b1+b2)*c1+1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1):

c3:=(a2+a1*b1+b2)*c1*(1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1)):

c4:=1+(a2*b1*a1*b2+1)*(a2*b1*c2+1)*(a1*b2*c2+1):

c5:=1+(a2*b2*c3+1)*(a2*b2*c4+1)*(c3*c4+1):

eqn := {a1+b1 = 1,

a2+a1*b1+b2+c1 = 1,

a2*b1+a1*b2+c2 = 1,

a2*b2+c3+c4 = 0,

c5 = 0};

solve(eqn,{a1,a2,b1,b2}); # <= Maple can't solve this

# But the solution is:

a2:=0: a1:=1: # a0:=1, so that a= "011" binary = 3 decimal

b2:=1: b1:=0: # a0:=1, so that b= "101" binary = 5 decimal

# Where a=3 and b=5 are the factors of 15.

Ron Dotson

6/03/2004

-----BEGIN PGP SIGNATURE-----

Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

iQA/AwUBQL97thpqFjUCnHWBEQIOeQCgpMXLFGkaEsNQ/nshYRRMxNVi3+8An3RQ

20UaohAI3jTT0B9S1XCz0Fj2

=Zgga

-----END PGP SIGNATURE----- - On Thu, 3 Jun 2004, Ron wrote:

>

Actually one can solve the system eqn with Maple (in two ways):

> n:= [0,0,1,1,1,1]: # factor binary 001111 = decimal 15 = 3*5

>

> c1:=a1*b1:

> c2:=(a2+a1*b1+b2)*c1+1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1):

> c3:=(a2+a1*b1+b2)*c1*(1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1)):

> c4:=1+(a2*b1*a1*b2+1)*(a2*b1*c2+1)*(a1*b2*c2+1):

> c5:=1+(a2*b2*c3+1)*(a2*b2*c4+1)*(c3*c4+1):

>

> eqn := {a1+b1 = 1,

> a2+a1*b1+b2+c1 = 1,

> a2*b1+a1*b2+c2 = 1,

> a2*b2+c3+c4 = 0,

> c5 = 0};

>

> solve(eqn,{a1,a2,b1,b2}); # <= Maple can't solve this

First way: (note in this case one has free variables b1,b2,c1,c4 so we

allow them to be any of 0 or 1 and see what works)

Sol:=solve(eqn);

2

Sol := {c5 = 0, a1 = -b1 + 1, a2 = b1 - b1 - b2 - c1 + 1,

3 2

c2 = -b1 + b1 + 2 b2 b1 + b1 c1 - b1 - b2 + 1,

2 2

c3 = -b2 b1 + b2 b1 + b2 + b2 c1 - b2 - c4, b1 = b1,

b2 = b2, c1 = c1, c4 = c4}

> for b1 from 0 to 1 do

Second way: Us msolve to solve modulo 2. It gives 5 solutions, but it can

> for b2 from 0 to 1 do

> for c1 from 0 to 1 do

> for c4 from 0 to 1 do

> a:=eval(a2*4+a1*2+1,Sol);

> b:=eval(b2*4+b1*2+1,Sol);

> if a*b = 15 then print(a,b); fi;

> od;

> od;

> od;

> od:

pick the one that works: (It may just be luck that this works?) Here's

how:

> eqn := {a1+b1 = 1,

Sol := {c5 = 0, b1 = 1, a1 = 0, c2 = 1, c1 = 1, a2 = 0, b2 = 0,

> a2+a1*b1+b2+c1 = 1,

> a2*b1+a1*b2+c2 = 1,

> a2*b2+c3+c4 = 0,

> c5 = 0}:

> Sol:=msolve(eqn,2);

c3 = c4}, {c5 = 0, b1 = 1, a1 = 0, c2 = 1, c1 = 0, b2 = 1,

a2 = 0, c3 = c4}, {c5 = 0, b1 = 1, a1 = 0, a2 = 1, c1 = 0,

b2 = 0, c3 = c4, c2 = 0}, {c5 = 0, b1 = 1, a1 = 0, a2 = 1,

c1 = 1, b2 = 1, c2 = 0, c3 = c4 + 1}, {c5 = 0, a1 = 1, c2 = 1,

c1 = 1, a2 = 0, b2 = 0, c3 = c4, b1 = 0}

> for i from 1 to nops([Sol]) do

5, 3

> a:=eval(a2*4+a1*2+1,Sol[i]);

> b:=eval(b2*4+b1*2+1,Sol[i]);

> if a*b = 15 then print(a,b); fi

> od:

I'm not sure why we don't also get 3,5 this way.

--Edwin Clark

>

--

> # But the solution is:

>

> a2:=0: a1:=1: # a0:=1, so that a= "011" binary = 3 decimal

> b2:=1: b1:=0: # a0:=1, so that b= "101" binary = 5 decimal

>

> # Where a=3 and b=5 are the factors of 15.

>

> Ron Dotson

> 6/03/2004

>

> -----BEGIN PGP SIGNATURE-----

> Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

>

> iQA/AwUBQL97thpqFjUCnHWBEQIOeQCgpMXLFGkaEsNQ/nshYRRMxNVi3+8An3RQ

> 20UaohAI3jTT0B9S1XCz0Fj2

> =Zgga

> -----END PGP SIGNATURE-----

>

>

>

>

> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

>

>

>

> Yahoo! Groups Sponsor

> ADVERTISEMENT

> click here

> [rand=153996665]

>

> ________________________________________________________________________________

> Yahoo! Groups Links

> * To visit your group on the web, go to:

> http://groups.yahoo.com/group/primenumbers/

>

> * To unsubscribe from this group, send an email to:

> primenumbers-unsubscribe@yahoogroups.com

>

> * Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

>

>

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

W. Edwin Clark, Math Dept, University of South Florida

http://www.math.usf.edu/~eclark/

--------------------------------------------------------- - --- In primenumbers@yahoogroups.com, Edwin Clark <eclark@m...> wrote:
>

-----BEGIN PGP SIGNED MESSAGE-----

> Actually one can solve the system eqn with Maple (in two ways):

>

Hash: SHA1

Very perceptive Edwin. I didn't know we had any Maple users

in this group. You are correct that if you copy/paste the

following lines into a Maple worksheet:

c1:=a1*b1:

c2:=(a2+a1*b1+b2)*c1+1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1):

c3:=(a2+a1*b1+b2)*c1*(1+(a2*a1*b1+1)*(a2*b2+1)*(a1*b1*b2+1)):

c4:=1+(a2*b1*a1*b2+1)*(a2*b1*c2+1)*(a1*b2*c2+1):

c5:=1+(a2*b2*c3+1)*(a2*b2*c4+1)*(c3*c4+1):

eqn := {a1+b1 = 1,

a2+a1*b1+b2+c1 = 1,

a2*b1+a1*b2+c2 = 1,

a2*b2+c3+c4 = 0,

c5 = 0}:

Sol:=msolve(eqn,2);

Maple provides the solutions immediately:

Sol := {a1 = 0, b1 = 1, a2 = 1, b2 = 0},

{a1 = 1, b1 = 0, a2 = 0, b2 = 1}

I should have used "msolve()" in my example instead of

"solve()." *However*, if you use the actual RSA-640 carry

definitions and equations (all 135MB of them!) instead of the

equations in this simple example, Maple's "msolve()" also fails.

If you don't include the carry definitions it fails immediately,

and if you include them it runs for awhile (hours) and then

terminates with an "Out of Memory" error while trying to expand

the carry definitions (if I recall correctly). If anyone wants

to try it themselves, you can download the carry definition file

(Carries.txt) and the equation file (equ.dat) as a single gzipped

tar file from:

http://snipurl.com/6uqu/rsa640.tar.gz

or as a Windows ZIP file from:

http://snipurl.com/6uqu/rsa640.zip

(They are both about 10MB in size)

To have Maple try to solve them, paste the following

into a Maple worksheet and execute it from the same directory

you unzipped "equ.dat" and "Carries.txt" into:

restart:

print("Reading Equations");

read "equ.dat":

print("Reading Carries");

read "Carries.txt":

print("Solving");

Sol:=msolve(equ,2);

Maybe it will work on a computer that's faster than

mine and has more RAM, but I doubt it. I have

an Athlon 1.1 GHz AMD processor with 1 GB RAM.

Ron Dotson

6/04/2004

-----BEGIN PGP SIGNATURE-----

Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com>

iQA/AwUBQMA8TRpqFjUCnHWBEQJCuACgiJx8iXGukS9pxZpbIsNBtwbRG5gAn29u

PVyC48adMZA1O0PDOq7aJfFL

=ulm/

-----END PGP SIGNATURE----- - Hi Ron,

R> Justin asked me for a real life example of how this technique

R> can be used to find factors, so at the risk of boring everyone

R> else, I thought I'd post it here on the forum. Here is a sample

R> Maple code snippet ('#' begins a comment) that illustrates the

R> problem:

Thanks Ron. I think I've finally understood the idea of the technique. I

also understand long-hand multiplication at long last ;)

R> n:= [0,0,1,1,1,1]: # factor binary 001111 = decimal 15 = 3*5

R> eqn := {a1+b1 = 1,

R> a2+a1*b1+b2+c1 = 1,

R> a2*b1+a1*b2+c2 = 1,

R> a2*b2+c3+c4 = 0,

R> c5 = 0};

As you know, these equations in the Z(2) field are equivalent to boolean

expressions. So they can be transformed the following way to eliminate the

equality:

lhs == 1 -> lhs

lhs == 0 -> NOT(lhs) -> lhs+1 (equivalent to NOT using only xor)

now all the ex-equations can be combined to one with AND (ie multiplication

in Z(2)) to form one expression:

(a1+b1) (a2+a1*b1+b2+c1) (a2*b1+a1*b2+c2) (a2*b2+c3+c4+1) (c5+1)

This can be reduced algebraically and transformed to boolean:

(a1 && b2 && ! a2 && ! b1) || (a2 && b1 && ! a1 && ! b2)

Which in effect is indeed your solution:

R> # But the solution is:

R> a2:=0: a1:=1: # a0:=1, so that a= "011" binary = 3 decimal

R> b2:=1: b1:=0: # a0:=1, so that b= "101" binary = 5 decimal

R> # Where a=3 and b=5 are the factors of 15.

I use Mathematica, and am not familiar with Maple, but I suppose it is

just as capable of these transformations.

I'm not sure about the practicability though. It already took a few seconds

to reduce your example expressions (albeit with somewhat straightforward

and probably not really efficient reduction algorithm).

But then, what do I know? ;P

--

Justin

ICQ 37456745

AIM jasticle