用辗转相除法求自然数e关于模φ的逆
本帖最后由 ashleytgg 于 2020-2-23 15:32 编辑欧几里得的辗转相除除法是数论中最基本的定律，但我用lisp 把它结合起来，觉得还是很有点乐趣，所有和大家分享下。
;;用辗转相除法 求两个自然数的 最大公约数相对应的lsp 函数为 (gcd a b)
;; output_mode 为输出方式，默认状态下输出 最大公约数，否则输出 辗转相除法的点对
(defun seek_greatest_common_divisor
(a b output_mode / temp r group_pair)
(if (< a b)
(setq temp a
a b
b temp
)
)
(setqgroup_pair
(list (list a b))
)
(while (/= (setq r (rem a b))
0
)
(setq a b
b r
group_pair
(cons (list a b) group_pair)
)
)
(setq group_pair (reverse group_pair))
(if output_mode
group_pair
b
)
)
;; ( seek_greatest_common_divisor (*2 3 5 7)(* 137 7 59 3 ) t )
;; (gcd (*2 3 5 7)(* 137 7 59 3 ) )
;;( seek_greatest_common_divisor3120 17 t )
;; 定义一个二元列表(a b) 乘以一个数 (a b)* c = (ab bc)
(defun XC (lst c /)
(list(* (car lst) c)
(* (cadr lst) c)
)
)
;;定义一个二元列表相加的函数
(defun ++ (lst1 lst2 lst3 / lst)
(mapcar '+ lst1 lst2 lst3)
)
;; 求 一次整数方程 ed + kφ= 1的解 , 其中 e 和 φ 是 互素的
;; (setq e 79φ_module 3120 )
(defun seek_inverse_of_module
(e φ_module / group lst i x y d)
(if (or (null e)
(null φ_module)
)
(setq e 17
φ_module 3120
)
)
;; 把e 限制在 模φ_module 的最小剩余系内
(setq e (rem e φ_module))
;; 当 (e φ_module) 是互质数时，程序进入计算，否则ed ≡1 (mode φ_module ) 无解
(if (and (= (gcd e φ_module) 1)
(/= e 1)
)
(progn
(setq
;; 用辗转相除法 求出 312017 的点对group ( (3120 17) (17 9) (9 8) (8 1) )
group
(seek_greatest_common_divisor e φ_module t)
group (reverse group)
;; 当group((8 1) (9 8) (17 9) (3120 17))第一一个元素 8能够整除1 时，去掉这个元素，为了程序计算需要
group (cdr group)
;; 把group((9 8) (17 9) (3120 17))中每个元素比如 3120/17 的商183加入到 (3120 17 183)
group
(mapcar '(lambda (lst / dividend divisor)
(mapcar 'set '(dividend divisor) lst)
(list dividend divisor (/ dividend divisor))
)
group
)
)
;|程序说明:
用辗转相除法求方程 ed + kφ= 1 的e 关于模 φ 的逆
group 结构为 ( (9 8 1) (17 9 1) (3120 17 183))
9= 3120 + 17*(-183)
8= 17 + 9* (-1)
答案1:1 = 9*(1) + 8* (-1) ==> 1 = 9 + * (-1)
答案2:==> 1= 17* (-1) + 9* 2
==> 1= 17* (-1) + *2
答案3: ==> 1= 3120*2+17* (-367)
答案1 、答案2、答案3 的解系数为: ( (1 -1) (-1 2) (2 -367) )
|;
(setq i 0)
(mapcar '(lambda (lst / dividend divisor quotient lst_2)
(mapcar 'set '(dividend divisor quotient) lst)
;; x y dividend divisor 之间的关系( dividend divisor)* (x y)T =1
(if (= i 0)
;; lst 为 group 的初始项时
(setq x 1
y (* -1 quotient)
)
(progn
(setq lst_2 (++
(XC (list 0 divisor) x)
(XC (list dividend 0) y)
(XC (list 0 (* -1 divisor quotient))
y
)
)
x (/ (car lst_2) dividend)
y (/ (cadr lst_2) divisor)
)
)
)
;| 当lst 不是group 中的 第一项时
(dividend divisor)* (x y)T ==(dividend_前 (dividend-divisor*商) )(x y)T
而 divisor_前 前一项的被除数 就等于当前项的 除数 divisor
|;
(setq i (1+ i))
(list x y)
)
group
)
;;方程 ey ≡1 (mode φ_module ) 的e 关于模 φ 的逆 为 y
(cond
((< (rem y φ_module) 0)
(+ (rem y φ_module) φ_module)
)
((> (rem y φ_module) φ_module)
(- (rem y φ_module) φ_module)
)
(t
(rem y φ_module)
)
)
)
;;当 (e φ_module) 不是互质数时 或 e =1 时
(progn
(cond
((= e 1)
(setq y 1)
)
(t
(princ "您说输入的参数无解!\n")
)
)
)
)
;; (if(and (= (gcd e φ_module) 1) 函数结束
)
;|(defun seek_inverse_of_module函数结束 ) (defun seek_inverse_of_module函数结束 ) (defun seek_inverse_of_module函数结束 )
(setq φ_module 3120)(setq φ_module 11018)
;; 验证程序的正确性
(mapcar '(lambda (e)
(setq
d (seek_inverse_of_module e φ_module)
)
(if (numberp d)
(cond
((< (rem (* e d) φ_module) 0)
(+ (rem (* e d) φ_module) φ_module)
)
((> (rem (* e d) 3120) φ_module)
(- (rem (* e d) 3120) φ_module)
)
(t
(rem (* e d) φ_module)
)
)
"无解"
)
)
(list 4 1317 61 83 97113 151
211 281379 509 683 91112171627
21792909388169079209
)
)
(seek_inverse_of_module 13120 )
|;
(defun C:辗转相除法
(/ dcl_file dcl_id
key lst_ keys
φ_module group_residual_system
i group
)
;; 定义一个用数组group_residual_system 填充列表框 "list_φ" 的函数
(defun add_list_list_φ (group_residual_system / i)
(start_list "list_φ")
(setq i 1)
(mapcar '(lambda (x)
(add_list (strcat "第" (itoa i) "个元素:" (itoa x)))
(setq i (1+ i))
)
group_residual_system
)
(end_list)
)
;; ( add_list_list_φgroup_residual_system )
;; 定义一个函数求模φ_module 的最简剩余系
(defun create_residual_system(φ_module / group_residual_system i)
(setq i 1
group_residual_system
nil
)
(repeat (1- φ_module)
(if (= (gcd i φ_module) 1)
(setq group_residual_system
(cons i group_residual_system)
)
)
(setq i (1+ i))
)
(reverse group_residual_system)
)
;; (setq group_residual_system (create_residual_systemφ_module))
(vl-load-com)
;; 创建一个dcl临时文件，并加载该文件，返回关键字 dcl_id
(setq dcl_id (create_tmp_dcl))
(new_dialog "tang_dcl" dcl_id)
(setqφ_module (read (get_tile "φ"))
;; 求模φ_module 的 最简剩余系
group_residual_system (create_residual_system φ_module)
)
;; 对列表框"list_φ" 进行填充
(add_list_list_φ group_residual_system)
;; 对txt 控件 "tang1" 进行赋值
(set_tile "tang1"
(strcat "模" (itoa φ_module) "的最简剩余系:")
)
(set_tile "tang2"
(strcat "共" (itoa (length group_residual_system)) "个元素")
)
;;定义各控件 的动作函数
(foreach key '("list_φ" "cacuate" "φ" "e")
(action_tile key "(Action_辗转相除法$key $value )")
)
(defun Action_辗转相除法 (key value / lst)
(cond
((= key "list_φ")
(setq e (nth (read value) group_residual_system))
(mapcar '(lambda(x value)
(set_tile x value)
)
(list "e" "d")
(list (itoa e) "")
)
)
;; 计算按钮的动作函数 求ed ≡1 (mode φ_module ) 的解 d
((= key "cacuate")
(setq e (get_tile "e")
φ_module (read (get_tile "φ"))
)
(if (and
;; (read value) 是数值
(numberp (VL-CATCH-ALL-APPLY
'read
(list e)
)
)
;; (read value) 是整数
(= (type (setq e (read e))) 'int)
;; (read value) 是>1 的整数
(> e 0)
)
(progn
(setq
d (seek_inverse_of_module e φ_module)
)
(if (numberp d)
(set_tile "d" (itoa d))
;; 当 ed ≡1 (mode φ_module )无解时
(set_tile "d" "无解")
)
)
(progn
(alert "你的输入的e有误，请重新输入!")
(mode_tile "e" 2)
)
)
;;if(and(numberp (VL-CATCH-ALL-APPLY
)
;;编辑框"φ" 的动作函数
((= key "φ")
(if (and
;; (read value) 是数值
(numberp (VL-CATCH-ALL-APPLY
'read
(list value)
)
)
;; (read value) 是整数
(= (type (read value)) 'int)
;; (read value) 是>1 的整数
(> (read value) 1)
)
;; 当value 是 整数时
(progn
;; 对txt 控件 "tang1" 进行赋值
(set_tile "tang1"
(strcat "模" value "的最简剩余系:")
)
(setq
group_residual_system
(create_residual_system (read value))
)
;; 对列表框"list_φ" 进行填充 ，当group_residual_system 的个数大于1万个时，只填充前1万项
(if (< (length group_residual_system) 10000)
(add_list_list_φ group_residual_system)
(progn
(setq group nil)
(repeat 10000
(setq group (cons 0 group))
)
;; 取group_residual_system 中的前1万项
(add_list_list_φ
(mapcar '+ group_residual_system group)
)
(set_tile
"tang3"
"只显示前1万项!"
)
)
;;(if (< (length group_residual_system) 10000)
)
;; (if (> (length group_residual_system) 10000)
(set_tile
"tang2"
(strcat "共"
(itoa (length group_residual_system))
"个元素"
)
)
)
;; progn 函数结束
(progn
;; 当value 不是整数，或者是等于1 时
(alert "你的输入有误，请重新输入!")
(mode_tile key 2)
)
)
;;if(and(numberp (VL-CATCH-ALL-APPLY
(set_tile "d" "")
)
;;编辑框"φ" 的动作函数 结束
((= key "e")
(set_tile "d" "")
)
)
;;cond 函数结束
)
;; (defun Action_辗转相除法 (key value
(setq Dialog_Return (start_dialog))
(unload_dialog dcl_id)
)
;; (defun C:辗转相除法函数结束
;; 创建一个临时dcl 文件 ,并打开它，返回关键字dcl_id
(defun create_tmp_dcl (/ f TMPDCL dcl_id)
(setqgroup_str
'(""
"tang_dcl:dialog"
"{"
" label = \"用欧几里得辗转相除法解同余方程：ed ≡1 (mode φ) \" ;"
" spacer;"
" :boxed_row"
" {"
" alignment = centered ;"
" children_fixed_width = true ;"
" fixed_height = true ;"
" fixed_width = true ;"
" :column"
" {"
" :text"
" {"
" label = \"模φ的最简剩余系:\" ;"
" key =\"tang1\" ;"
" }"
" :text"
" {"
" label = \"共8个元素\" ;"
" key =\"tang2\" ;"
" }"
" :text"
" {"
" label = \"\" ;"
" key =\"tang3\" ;"
" }"
" :list_box"
" {"
" fixed_height = false ;"
" fixed_width = true ;"
" is_tab_stop = true ;"
" key = \"list_φ\" ;"
" width = 20 ;"
" }"
" }"
" :column"
" {"
" fixed_height = true ;"
" :edit_box"
" {"
" edit_width = 8 ;"
" is_enabled = true ;"
" key = \"e\" ;"
" label = \"方程ed ≡1 (mod φ)的e\" ;"
" value=\"17\" ;"
" }"
" :edit_box"
" {"
" edit_width = 8 ;"
" key = \"φ\" ;"
" label = \"方程ed ≡1 (mod φ)的φ\" ;"
" value=\"3120\" ;"
" }"
" :row"
" {"
" :button"
" {"
" key = \"cacuate\" ;"
" fixed_width = true ;"
" label = \"计算e对模φ的逆: d\" ;"
" width = 6 ;"
" }"
" :edit_box"
" {"
" edit_width = 8 ;"
" key = \"d\" ;"
" label = \"\" ;"
" }"
" }"
" }"
" }"
" :row"
" {"
" alignment = centered ;"
" children_fixed_width = true ;"
" fixed_width = true ;"
" spacer_1;"
" :button"
" {"
" is_cancel = true ;"
" key = \"cancel\" ;"
" label = \"取消\" ;"
" width = 15 ;"
" }"
" }"
"}"
)
)
(SETQ TMPDCL (VL-FILENAME-MKTEMP "tmp" "" ".dcl"))
(setq f (open tmpdcl "w"))
(foreach str group_str
(write-line str f)
)
(close f)
(setq dcl_id (load_dialog TMPDCL))
(vl-file-delete TMPDCL)
dcl_id
)
;;( create_tmp_dcl )
好好学习下~~~ :handshake，
页:
[1]