[發明專利]時間復雜度取決于大整數乘法的大整數除法

無效

• 申請號: 201110355091.7
• 申請日: 2011-11-01
• 公開（公告）號: CN103092568A
• 公開（公告）日: 2013-05-08
• 發明（設計）人: 劉海云
• 申請（專利權）人: 劉海云
• 主分類號: G06F9/30
• 分類號: G06F9/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明主要提供一種特殊的分治遞歸運算的大整數除法(包括整除的商值及整除后取余數)。這種算法主要應用于計算機領域，尤其是加密技術中。

發明背景

當前公開或使用的大整數除法即使采用Knuth的經典名著“The?Art?ofComputer?Programming”的第4.3.1節中的猜商值公式來計算，也需要多次試運算，所有這些大整數除法最大的缺點是時間復雜度：T(n)＝O(n²)這與大整數乘法相比差遠了。因此減少試運算的次數，降低時間復雜度對大整數除法具有特別重要的意義。本文依據全新的計算理論，構造了獨特的大整數除法計算方法，文中實施例使試運算出現的概率遠低于現有算法，即使出現也只需一次加法運算，不僅如此，更為重要的是本文采用特殊的分治遞歸的方法充分利用大整數乘法，使大整數除法的時間復雜度等于大整數除法中所采用的大整數乘法的時間復雜度，例如大整數除法中采用Karatsuba乘法加速時，本文中的大整數除法時間復雜度：如果采用其他更快的大整數乘法，本算法會更快，這就使數值很長的大整數除法的計算速度大幅提高，例如當被除數的長度為4194304個四字節，除數長度為2097152個四字節時，本算法中采用Karatsuba乘法加速時的速度為現有大整數除法速度的30倍左右。

發明內容

本文在這部分將推出一種全新的大整數除法計算理論，并利用該理論構造分治的大整數除法，在分治中充分利用大整數乘法，以達到加速目的。請看下面的推理：

設大整數運算過程中采用h(大于1的整數)進制，

正整數集合：Z＝{x|????x＞0并且[x]＝x}

集合1：H＝{x|?????0≤x＜h并且x為整數}

集合2：H₂＝{x|????1≤x＜h并且x為整數}

任何有限長度的大整數除法都可轉化為非負大整數的除法，因此除了最后一段外，下文只涉及非負大整數除法，非負大整數除法可表示如下：

C＝A/B??(A≥0，B＞0，C≥0并且A和B都是整數)????(1)

當A＝0時，顯然C＝0，??????????????????????????(2)

當A＜B時，顯然C的整數部分為0，????????????????(3)

當A≥B時，可通過將被除數和除數都乘以h^m從而使A和B都轉化為不小于h^m的整數，并使結果C保持不變，其中m≥2且m∈Z，因此(1)式在排除(2)、(3)后，可轉化為下式：

C＝A/B????(A≥B，B≥h^m，m≥2，C＞0且A、B和m都是正整數)????(4)

在(4)中A＝(A₁A₂A₃…A_i-1A_i)h可用多項式表示如下：

A＝A₁h^i-1+A₂h^i-2+A₃h^i-3+…+A_i-1h¹+A_i????????(5)

其中i∈Z，A₁∈H₂，A_r∈H(1＜r≤i，且r為整數)，h為進制基數，用A_H表示A的前m項，即

A_H＝A₁h^i-1+A₂h^i-2+A₃h^i-3+…+A_m-1h^i-(m-1)+A_mh^i-m????(6)