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

在審

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

本發明提供了一種計算機加密中帶容差的最大公約數計算方法，包括：步驟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的帶容差的最大公約數。

技術領域

本發明涉及一種計算機加密技術，特別是一種計算機加密中帶容差的最大公約數計算方法。

背景技術

最大公約數是指兩個或多個整數共有約數中最大的一個，計算兩個整數的最大公約數問題是一個非常古老的問題，在古希臘與古代中國的著述中均有論述。求解最大公約數有多種方法，常見的有窮舉法、輾轉相除法(又稱歐幾里德算法) 和輾轉相減法(又稱更相減損法)。

窮舉法，是指從多個整數中的最小數開始由大到小的列舉，直到找到公約數為止，找到的公約數即為最大公約數。窮舉法簡單粗暴，計算量大。

輾轉相除法又稱歐幾里德算法，用來求兩個正整數最大公約數的算法。由古希臘數學家歐幾里德在其著作《TheElements》中最早描述了這種算法，所以被命名為歐幾里德算法。擴展歐幾里德算法可用于RSA加密等領域。

輾轉相減法又稱更相減損法，是出自《九章算術》的一種求最大公約數的算法，它原本是為約分而設計，但它適用于任何需要求最大公約數的場合。《九章算術》是中國古代的數學專著，其中的“更相減損術”可以用來求兩個數的最大公約數，即“可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。”

國內外對于最大公約數問題的研究集中于大數的最大公約數求解問題，主要應用于加密領域。與本文論述的設定容差條件下的最大公約數問題存在根本不同。本發明描述的是兩個整數在一定模糊條件下的最大公約數問題的求解。

發明內容

本發明的目的在于提供一種計算機加密中帶容差的最大公約數計算方法，包括以下步驟：

步驟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的具體過程為：

步驟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的大小關系，確定下一步遞歸調用的格式。

步驟23分3種情況進行討論：