Minimal arithmetic representation of a number n in relative base r for breaking down computing operations in particular cryptographic

摘要

The invention concerns a method for breaking down and performing with an electronic circuit, a computing operation based on a digital factor (N) expressed in integral base (r) by a series of integers (p_n−1, p₂, p₁, p₀). The invention provides steps which consists in: breaking down the series of integers into elementary multiplets, each elementary multiplet (M^j) comprising part of the series of integers (m^j_i+1, m^j_i, m^j₀), wherein each pair of successive numbers (m_i, m_i−1) has a sum equal in value to the base decreased by one unit (m_i+m_i1=r−1) and transforming each elementary multiplet (M^j) into a modified multiplet (S^j) comprising a series of sign digits (s^j_i,s_j−1, ,s^j₁)such that the concatenation of modified multiplets constitute a series of sign digits containing a minimum of non-null digits and representing the value of the digital factor (N) in a relative base ({−(r−1), ,−1,0,1, ,r−1}). In the preferred embodiment of the invention: for an elementary multiplet containing a minimum number of odd integers, and expressed in the following form: M1=[b,d,(c,d)^k,e] (type I) the transformation follows one of the following conditional formulae: {S1=|*,(d,c)^k, d,*], if b+dr−1 and e+dr−1, S1=[*, (d,c)^k, d+1, *], if b+dr−1 and e+dr−1, S1=[*, (−c,−d)^k, d−r, *], if b+dr−1 and e+dr−1, S1=[*,(−c,−d)^k, −d,*]* if b+dr−1 and e+dr−1) (1); for an elementary multiplet containing an even number of integers, and expressed in the following form: M2=[b,d,(c,d)^k,c,e] (type II) the transformation follows one of the following conditional formulae: {S2=[*,(d,c)^k,d,c,*], if b+dr−1 and e+cr−1, S2=[*,(d,c)^k, d+1, −d,*], if b+dr−1 and e+cr−1, S2=[*, (−c,−d)^k,d−r,c,*], if b+dr−1 and e+cr−1, S2=[*,(−c,−d)^k−c,−d,*], if b+dr−1 and e+cr−1 (2).