[發明專利]計算機加密中帶容差的最大公約數計算方法

在審

• 申請號: 201811617342.2
• 申請日: 2018-12-28
• 公開（公告）號: CN109886024A
• 公開（公告）日: 2019-06-14
• 發明（設計）人: 史敏;位飛;于志良;高祺;陳程;孫昊;高興建;何俊輝
• 申請（專利權）人: 中國航天科工集團八五一一研究所
• 主分類號: G06F21/60
• 分類號: G06F21/60
• 代理公司: 南京理工大學專利中心 32203
• 代理人: 朱寶慶

1.一種計算機加密中帶容差的最大公約數計算方法，其特征在于，包括以下步驟：

步驟1，采用輾轉相減的方法處理正整數A、B，其中被減數H＝Ha×A+Hb×B，減數L＝La×A+Lb×B，輾轉相減直至差值H-L≤(|Ha-La|+|Hb-Lb|)×T時，調用遞歸函數HLLH，Ha、Hb、La、Lb分別是A、B的系數，T是容差；

步驟2，進入遞歸函數HLLH(H，L，Ha，Hb，La，Lb)，計算符合條件的公約數G的集合；

步驟3，從符合條件的公約數G的集合中確定最大值G_max，G_max為設定條件下A與B的帶容差的最大公約數。

2.根據權利要求1所述的方法，其特征在于，步驟2的具體過程為：

步驟21，設定遞歸結束條件，即|Ha-La|>M或|Hb-Lb|>M；

步驟22，當|H-L|≤(|Ha-La|+|Hb-Lb|)×T時，執行步驟23，否則執行步驟24；

步驟23，當|H-L|≤(|Ha-La|+|Hb-Lb|)×T時，分情況進行討論，計算符合條件的最大公約數G或進一步進行遞歸調用；

步驟24，當|H-L|>(|Ha-La|+|Hb-Lb|)×T時，根據H與L的大小關系，確定下一步遞歸調用的格式。

3.根據權利要求2所述的方法，其特征在于，步驟23分3種情況進行討論：

(1)解方程-[(Ha-La)×Ta+(Hb-Lb)×Tb]＝H-L獲得的整數Ta、Tb，|Ta|≤T，|Tb|≤T；令a＝A+Ta，b＝B+Tb，采用歐幾里德算法求得a與b的最大公約數G；

(2)令NH＝H，NL＝L-H，NHa＝Ha，NHb＝Hb，NLa＝La-Ha，NLb＝Lb-Hb，調用遞歸函數HLLH(NH，NL，NHa，NHb，NLa，NLb)；

(3)令NH＝L，NL＝H-L，NHa＝La，NHb＝Lb，NLa＝Ha-La，NLb＝Hb-Lb，調用遞歸函數HLLH(NH，NL，NHa，NHb，NLa，NLb)。

4.根據權利要求2所述的方法，其特征在于，步驟24相關步驟如下：

步驟241，比較H與L的關系，如果H≥L，執行步驟242，否則執行步驟243；

步驟242，令NH＝L，NL＝H-L，NHa＝La，NHb＝Lb，NLa＝Ha-La，NLb＝Hb-Lb，調用遞歸函數HLLH(NH，NL，NHa，NHb，NLa，NLb)；

步驟243，當H<L時，令NH＝H，NL＝L-H，NHa＝Ha，NHb＝Hb，NLa＝La-Ha，NLb＝Lb-Hb，調用遞歸函數HLLH(NH，NL，NHa，NHb，NLa，NLb)。