]> git.cryptolib.org Git - arm-crypto-lib.git/blob - gcdext-test.rb
705b42a53008037f89b3b685fb47058f24656f40
[arm-crypto-lib.git] / gcdext-test.rb
1 #!/usr/bin/ruby
2 # gcdext-test.rb
3 =begin
4     This file is part of the AVR-Crypto-Lib.
5     Copyright (C) 2008, 2009  Daniel Otte (daniel.otte@rub.de)
6
7     This program is free software: you can redistribute it and/or modify
8     it under the terms of the GNU General Public License as published by
9     the Free Software Foundation, either version 3 of the License, or
10     (at your option) any later version.
11
12     This program is distributed in the hope that it will be useful,
13     but WITHOUT ANY WARRANTY; without even the implied warranty of
14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15     GNU General Public License for more details.
16
17     You should have received a copy of the GNU General Public License
18     along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 =end
20
21 $debug = true
22 $debug = false
23 require 'rubygems'
24 require 'serialport'
25 require 'getopt/std'
26 require 'ftools'
27 require 'date'
28
29 def gcdext(x,y)
30   g=1
31   i=0
32   while(x&1==0 && y&1==0) do
33     x>>=1
34     y>>=1
35     g<<=1
36     i+=1
37   end
38   printf("DBG: initshift = %04X\n", i)
39   u=x; v=y; a=1; b=0; c=0; d=1
40   begin
41     printf(" while u%%2==0; u = %X\n", u)
42     printf("DBG: (10) a = %s\n", a.to_s(16).upcase)
43     printf("DBG: (10) b = %s\n", b.to_s(16).upcase)
44     printf("DBG: (10) c = %s\n", c.to_s(16).upcase)
45     printf("DBG: (10) d = %s\n", d.to_s(16).upcase)
46     while(u&1==0) do
47       if(a%2==1 || b%2==1)
48         a += y
49         b -= x
50       end
51       u>>=1; a>>=1; b>>=1
52     end
53     printf(" while v%%2==0; v = %X\n", v)
54     printf("DBG: (20) a = %s\n", a.to_s(16).upcase)
55     printf("DBG: (20) b = %s\n", b.to_s(16).upcase)
56     printf("DBG: (20) c = %s\n", c.to_s(16).upcase)
57     printf("DBG: (20) d = %s\n", d.to_s(16).upcase)
58     while(v&1==0) do
59       if(c%2==1 || d%2==1)
60         c += y
61     #    printf("DBG: (qq) b = %s\n", b.to_s(16).upcase)
62         d -= x
63       end
64       printf("DBG: (xx) d = %s\n", d.to_s(16).upcase) 
65       v>>=1; c>>=1; d>>=1;
66     end
67     
68     printf(" if u>=v ...\n")
69     printf("DBG: (30) a = %s\n", a.to_s(16).upcase)
70     printf("DBG: (30) b = %s\n", b.to_s(16).upcase)
71     printf("DBG: (30) c = %s\n", c.to_s(16).upcase)
72     printf("DBG: (30) d = %s\n", d.to_s(16).upcase)
73
74     if(u>=v)
75       u -= v; a-=c; b-=d
76     else
77       v -= u; c-=a; d-=b
78     end
79   end while(u!=0)
80   return[g*v, c, d]
81 end
82
83
84 if ARGV.length==2
85   a = ARGV[0].to_i
86   b = ARGV[1].to_i
87 else
88   # CD319349, 9EFD76CC
89   # 1609000771, 6fac577d72
90   a = 0x1609000771
91   b = 0x6fac577d72
92 end
93 r = gcdext(a, b)
94 printf("gcdext( %s, %s) => a = %s; b = %s; gcd = %s\n",
95   a.to_s(16),b.to_s(16),r[1].to_s(16),r[2].to_s(16),r[0].to_s(16))
96
97