#!/usr/local/bin/wish
#Z/2[x] calculator version 1.0
#Copyright 2000 Felipe Voloch (voloch@math.utexas.edu)
#
#Operations with polynomials with Z/2 coefficients
#and modular arithmetic thereof (if checkbutton is on).
#Polys read from left to right (ie 01001 is x+x^4),
#the button + adds, the button x multiplies and the button % takes remainder.
#The  button ^ takes power but you have to enter the exponent by hand.
#You can replace the modulus with the polynomial of your choice.

button .b0 -text "0" -command {.new insert end 0}
button .b1 -text "1" -command {.new insert end 1}
button .bt -text "x" -command {set old $new;set new "";set c t}
button .bp -text "+" -command {set old $new;set new "";set c p}
button .br -text "%" -command {set old $new;set new "";set c re}
button .bpo -text "^" -command {set old $new;set new "";set c po}
button .be -text "=" -command \
{if {$c == "p"} {
set res [Flipmod [Plus $old $new]] 
} elseif {$c == "t"} {
set res [Flipmod [Times $old $new]]
} elseif {$c == "re"} {
set res [Rem $old $new]
} elseif {$c == "po"} {
set res [Pow $old $new]
} 
}
button .bc -text "C" -command {set res "";set old "";set new ""}
entry .entry -width 20 -relief sunken -textvariable res -font {Times 14}
entry .old -width 20 -relief sunken -textvariable old -font {Times 14}
entry .new -width 20 -relief sunken -textvariable new -font {Times 14}
entry .modulus -width 10 -relief sunken -textvariable m -font {Times 14}
label .l -text "mod:"
set m "111"
checkbutton .mod -variable mod

grid .old -row 0 -column 0 -columnspan 4
grid .new -row 1 -column 0 -columnspan 4
grid .entry -row 2 -column 0 -columnspan 4
grid .b0 -row 3 -column 0
grid .b1 -row 4 -column 0
grid .bp -row 3 -column 1
grid .bt -row 4 -column 1
grid .br -row 3 -column 2
grid .bc -row 3 -column 3
grid .be -row 4 -column 2
grid .bpo -row 4 -column 3
grid .mod -row 5 -column 0
grid .l -row 5 -column 1
grid .modulus -row 5 -column 2 -columnspan 2

################################################
#toggles between straight and modular arithmetic
################################################

proc Flipmod {a} {
global m mod
if {$mod == 1} {
set r [Rem $a $m]
} else {
set r $a
}
return $r
}

######
#Math#
######

#######################
#the product of a and b
#######################

proc Times {a b} {
set r 0
set s $a
set n [string length $b]
for {set i 0} {$i < $n} {incr i} {
if {[string index $b $i] == 1} {
set r [Plus $r $s]
}
set s 0$s
}
return $r
}

#######################
#the sum of a and b
#######################

proc Plus {a b} {
set t $a
set n [string length $b]
if {[string length $a] < $n} {
set n [string length $a]
set t $b
}
set s ""
for {set i 0} {$i < $n} {incr i} {
set s [append s [expr {[string index $a $i]^[string index $b $i]}]]
}
set r [append s [string range $t $n [string length $t]]]
return $r
}

####################################
#the remainder of division of a by b
####################################

proc Rem {a b} {
set r $a
set n [string length $b]
while {$n <= [string length $r]} {
set r [Fix [Plus $r [Exm $b [expr {[string length $r] - $n}]]]]
}
return $r
}

########################################################
#Removes zeros at the end. Needed for Rem and useful for display
########################################################

proc Fix {c} {
set n [string last "1" $c]
if {$n == -1} {
set r 0
} else {
set r [string range $c 0 $n]
}
return $r
}

########################################################
#Outpts a with k zeros in front. Needed for Rem
########################################################

proc Exm {a k} {
set x "01"
set r $a
if {$k > 0} {
for {set i 1} {$i <= $k} {incr i} {
set r [Times $x $r]
}
}
return $r
}

########################################################
# Pow is a to the power b. Knows when to do modular.
# borrowed from the wiki
########################################################

proc Pow {a b} {
global mod m
if {$b == 0} {
return 1
} elseif {$b == 1} {
return $a
} else {
if {$b%2 == 0} {
set r [Pow $a [expr {$b/2}]]
if {$mod} {
return [Rem [Sq $r] $m]
} else {
return [Sq $r]
}
} else {
set r [Pow $a [expr {$b - 1}]]
if {$mod} {
return [Rem [Times $a $r] $m]
} else {
return [Times $a $r]
}
}
}
}

###############################
#Square of x
##############################

proc Sq {x} {
set n [string length $x]
set r [string index $x 0]
for {set i 1} {$i < $n} {incr i} {
append r 0
append r [string index $x $i]
}
return $r
}


###############################
#testing x^(1+q+...+q^n), n = 2^m
###############################

proc Sqm {x m} {
set r $x
for {set i 0} {$i < $m} {incr i} {
set r [Sq $r]
}
return $r
}

proc Phi {x n m} {
if {[expr {$n%2}]} {
set y [Phi [expr {$n/2}] $m]
set z [Sqm $y [expr {($n/2 + 1)*$m}]]
return [Times $y $z]
} else {
set y [Phi [expr {$n/2 -1}] $m]
set z [Times $x [Sqm $y $m]]
return [Times $y [Sqm $z [expr {($n/2)*$m}]]]
}
}