premise:
The complement of the analog number is smaller than the modulus itself;
definition:
Suppose: i = uint.maxvalue 1;
Integer a = A0 * I0 A1 * I1 A2 * I2 ... AE * IE; AI Mode M = M0 * I0 M1 * I1 M2 * I2 ... MK * IK; MI Solve: a% M solution: Set: n = ik 1-m; Because: mk> 0; So: N = N0 * I0 N1 * I1 N2 * I2 ... NK * IK; NI When e A% m = a; When e> k: Set: z = e-k-1; Because: i> = mk 1; and so: AE * i * IE-1> = mk * ae * IE-1 AE * IE-1; AE * IE> = ae * mk * ik z ae * ik z; AE * IE> = ae * iz * (mk * ik ik); because: IK> M0 M1 * I1 M2 * I2 ... MK-1 * IK-1; IK MK * IK> M; A> = ae * ie; and so: A> ae * IZ * m; A% m = (a-ae * IZ * m)% m; A% m = (a-ae * IZ * (IK 1-N))% M; A% m = (a-ae * IZ * IK 1 AE * IZ * N)% m; A% m = ((A0 A1 * I1 ... AE-1 * IE-1) AE * IZ * n)% m; A% M = ((A0 A1 * I1 ... AZ-1 * IZ-1) (AZ * IZ AZ 1 * IZ 1 ... AE-1 * IE-1) ae * iz * N)% m; A% m = ((A0 A1 * I1 ... AZ-1 * IZ-1) ((AZ * IZ AZ 1 * IZ 1 ... AE-1 * IE-1) AE * IZ * (N0 N1 * I1 ... NK * IK))))% M; A% m = ((A0 A1 * I1 ... AZ-1 * IZ-1) ((AZ * IZ AZ 1 * IZ 1 ... AE-1 * IE-1) AE * (N0 * IZ N1 * IZ 1 ... NK * IE-1)))))) M. A% m = ((A0 A1 * I1 ... AZ-1 * IZ-1) ((AZ AE * N0) * IZ (AZ 1 AE * N1) * IZ 1 ... (AE-1 AE * NK) * IE-1))% m; When e = k: When a When A> = M: Because: 2 * mk> i; so: 2 * m> a; M> a-m> = 0; A% m = a-m = a N-IK 1 = (A N)% IK 1; C # code implementation: From the author's CMS.Security.RSA class, please email: iswdj@263.net or QQ: ISWDJ@263.net or QQ: 228512046 to ask the author. /// /// Calculate the remainder of unsigned large integer modes without symbol. /// /// The rest of the number will change /// Enthemicals of the modulus, the smaller the value of the ADCM [Length-1], the faster the calculation, the faster /// Storage remainder value, array length should be equal to or greater than an array array length Private void mod (uint [] inx, uint [] adcm, uint [] OUTV) { / * * If your calling program cannot determine if the OUTV array length is equal to an array length, enable this statement. * Note that the length of the OUTV array cannot be less than the length of the analog number. * Array.clear (OUTV, 0, OUTV.LENGTH); * / INT I, IV; Uint Mult; Ulong Temp; INT LEN_X = Inx.Length; INT LEN_M = adcm.length; IF (len_x { Array.copy (Inx, 0, OUTV, 0, LEN_X); For (i = len_x; i Return; } While (- len_x> = len_m) { MULT = INX [LEN_X]; Inx [len_x] = 0; While (MULT> 0) { TEMP = 0; IV = len_x-len_m; For (i = 0; i { Temp = (ulong) ADCM [i] * Mult Inx [iv]; Inx [iv] = (uint) TEMP; TEMP >> = 32; IV ; } Mult = (uint) TEMP; } } TEMP = 0; For (i = 0; i { Temp = (Ulong) ADCM [i] Inx [i]; OUTV [I] = (uint) TEMP; TEMP >> = 32; } IF (Temp! = 1) Array.copy (Inx, 0, OUTV, 0, LEN_M); }
