📄 dilog.java
字号:
}
}
} /* end switch */
}
private void GetMontgomeryParms() {
int j;
long d,h,i,t,x,v;
dN = (double)TestNbr[NumberLength-1];
if (NumberLength > 1) {
dN += (double)TestNbr[NumberLength-2]/dDosALa32;
}
if (NumberLength > 2) {
dN += (double)TestNbr[NumberLength-3]/dDosALa64;
}
h = TestNbr[0];
i = DosALa32;
v = 0;
d = 1;
do {
t = i/h;
x = h;
h = i-t*x;
i = x;
x = d;
d = v-t*x;
v = x;
} while (h > 0);
MontgomeryMultN = (-v) & DosALa32_1;
j=NumberLength;
MontgomeryMultR1[j] = 1;
do {
MontgomeryMultR1[--j] = 0;
} while (j>0);
AdjustModN(MontgomeryMultR1);
MultBigNbrModN(MontgomeryMultR1,MontgomeryMultR1,MontgomeryMultR2);
MontgomeryMult(MontgomeryMultR2,MontgomeryMultR2,MontgomeryMultAfterInv);
AddBigNbrModN(MontgomeryMultR1,MontgomeryMultR1,MontgomeryMultR2);
}
private void BigNbrModN(long Nbr[], int Length, long Mod[]) {
int i,j;
for (i=0; i<NumberLength; i++) {
Mod[i] = Nbr[i + Length - NumberLength];
}
Mod[i] = 0;
AdjustModN(Mod);
for (i=Length - NumberLength - 1; i>=0; i--) {
for (j=NumberLength; j>0; j--) {
Mod[j] = Mod[j-1];
}
Mod[0] = Nbr[i];
AdjustModN(Mod);
}
}
private void MultBigNbrModN(long Nbr1[], long Nbr2[], long Prod[]) {
int i,j;
long Pr, Nbr;
i=NumberLength;
do {
Prod[--i] = 0;
} while (i>0);
i=NumberLength;
do {
Nbr=Nbr1[--i];
j=NumberLength;
do {
Prod[j] = Prod[j-1];
j--;
} while (j>0);
Prod[0] = 0;
Pr = 0;
for (j=0; j<NumberLength; j++) {
Pr = (Pr >>> 32) + Nbr*Nbr2[j] + Prod[j];
Prod[j] = Pr & DosALa32_1;
}
Prod[j] += (Pr >>> 32);
AdjustModN(Prod);
} while (i>0);
}
private void MultBigNbrByLongModN(long Nbr1[], long Nbr2, long Prod[]) {
long Pr;
int j;
Pr = 0;
for (j=0; j<NumberLength; j++) {
Pr = (Pr >>> 32) + Nbr2*Nbr1[j];
Prod[j] = Pr & DosALa32_1;
}
Prod[j] = (Pr >>> 32);
AdjustModN(Prod);
}
private void AdjustModN(long Nbr[]) {
long TrialQuotient;
long Cy;
int i;
double dAux;
dAux = (double)Nbr[NumberLength]*dDosALa32 + (double)Nbr[NumberLength-1];
if (NumberLength > 1) {
dAux += (double)Nbr[NumberLength-2]/dDosALa32;
}
TrialQuotient = (long)Math.ceil(dAux / dN) + 2;
if (TrialQuotient >= DosALa32) {
Cy = 0;
for(i=0; i<NumberLength; i++) {
Cy = Nbr[i+1]-(TrialQuotient>>>32)*TestNbr[i] - Cy;
Nbr[i+1] = Cy & DosALa32_1;
Cy = (DosALa32_1 - Cy) >>> 32;
}
TrialQuotient &= DosALa32_1;
}
Cy = 0;
for (i=0; i<NumberLength; i++) {
Cy = Nbr[i] - TrialQuotient*TestNbr[i] - Cy;
Nbr[i] = Cy & DosALa32_1;
Cy = (DosALa32_1 - Cy) >>> 32;
}
Nbr[NumberLength] -= Cy;
while ((Nbr[NumberLength] & DosALa32_1) != 0) {
Cy=0;
for (i=0; i<NumberLength; i++) {
Cy += Nbr[i]+TestNbr[i];
Nbr[i] = Cy & DosALa32_1;
Cy >>= 32;
}
Nbr[NumberLength] += Cy;
}
}
private boolean BigNbrIsZero(long Nbr[]) {
for(int i=0; i<NumberLength; i++) {
if (Nbr[i] != 0) {
return false;
}
}
return true;
}
/***********************************************************************/
/* NAME: ModInvBigNbr */
/* */
/* PURPOSE: Find the inverse multiplicative modulo v. */
/* */
/* ALGORITHM USED TO COMPUTE u^(-1) MOD v (assuming v odd): */
/* */
/* Step Y1. Set u1 <- 1, u3 <- u, v1 <- v, v3 <- v */
/* */
/* Step Y2. If u is odd, set t1 <- 0, t3 <- -v and go to step Y4 */
/* else, set t1 <- 1, t3 <- u. */
/* */
/* Step Y3. If t1 is even, set t1 <- t1/2, t3 <- t3/2 */
/* else, set t1 <- (t1+v)/2, t3 <- t3/2 */
/* */
/* Step Y4. If t3 is even, go back to step Y3. */
/* */
/* Step Y5. If t3 is positive, set u1 <- t1, u3 <- t3 */
/* else, set v1 <- v - t1, v3 <- -t3. */
/* */
/* Step Y6. Set t1 <- u1 - v1, t3 <- u3 - v3. */
/* */
/* Step Y7. If t1<0, set t1 <- t1 + v. */
/* */
/* Step Y8. If t3 is not zero, go back to step Y3. */
/* */
/* The algorithm terminates with u1 = u^(-1) MOD v. */
/***********************************************************************/
private void ModInvBigNbr(long[] u, long [] inv, long[] v) {
int i,NbrLength,NbrShifts;
int Pass = 0;
long Cy, Cy1, Result,Mask;
for (i=NumberLength/2-1; i>=0; i--) {
CalcAuxModInvU[i] = u[2*i] + (u[2*i+1] << 32) - DosALa63;
CalcAuxModInvV[i] = v[2*i] + (v[2*i+1] << 32) - DosALa63;
}
NbrLength = NumberLength/2;
if (NumberLength%2 == 1) {
CalcAuxModInvU[NbrLength] = u[NumberLength-1] - DosALa63;
CalcAuxModInvV[NbrLength] = v[NumberLength-1] - DosALa63;
NbrLength++;
}
// Step Y1. Set u1 <- 1, u3 <- u, v1 <- v, v3 <- v
CalcAuxModInvU1[0] = DosALa63+1;
CalcAuxModInvU3[0] = CalcAuxModInvU[0];
CalcAuxModInvV1[0] = CalcAuxModInvV3[0] = CalcAuxModInvV[0];
for (i=1; i<NbrLength; i++) {
CalcAuxModInvU1[i] = CalcAuxModInvT1[i] = DosALa63;
CalcAuxModInvU3[i] = CalcAuxModInvU[i];
CalcAuxModInvV1[i] = CalcAuxModInvV3[i] = CalcAuxModInvV[i];
}
// Step Y2. If u is odd, set t1 <- 0, t3 <- -v and go to step Y4
// else, set t1 <- 1, t3 <- u.
if ((CalcAuxModInvU[0] & 1) != 0) {
CalcAuxModInvT1[0] = DosALa63;
Cy = 0;
for (i=0; i<NbrLength; i++) {
CalcAuxModInvT3[i] = Cy - CalcAuxModInvV[i];
Cy = (Cy != 0 || CalcAuxModInvT3[i] != DosALa63? -1: 0);
}
}
else {
CalcAuxModInvT1[0] = DosALa63+1;
for (i=0; i<NbrLength; i++) {
CalcAuxModInvT3[i] = CalcAuxModInvU[i];
}
}
do {
if (Pass != 0 || (CalcAuxModInvT3[0] & 1) == 0) {
NbrShifts = 0; Mask = 1;
do {
// Step Y3. If t1 is even, set t1 <- t1/2, t3 <- t3/2
// else, set t1 <- (t1+v)/2, t3 <- t3/2
if ((CalcAuxModInvT1[0] & 1) != 0) {
Cy=DosALa63;
for (i=0; i<NbrLength; i++) {
Result = Cy + CalcAuxModInvT1[i] + CalcAuxModInvV[i];
if (Cy == DosALa63) {
Cy = (Result < CalcAuxModInvT1[i] || Result < CalcAuxModInvV[i]?
DosALa63+1: DosALa63);
}
else {
Cy = (Result <= CalcAuxModInvT1[i] || Result <= CalcAuxModInvV[i]?
DosALa63+1: DosALa63);
}
CalcAuxModInvT1[i] = Result;
}
}
for (i=0; i<NbrLength-1; i++) {
CalcAuxModInvT1[i] = (CalcAuxModInvT1[i] >>> 1 |
CalcAuxModInvT1[i+1] << 63)^AdjustDiv;
}
CalcAuxModInvT1[i] = ((CalcAuxModInvT1[i]^DosALa63) >>> 1) |
(CalcAuxModInvT1[i] & DosALa63);
// Step Y4. If t3 is even, go back to step Y3.
Mask *= 2;
if (++NbrShifts == 64) {
for (i=0; i<NbrLength-1; i++) {
CalcAuxModInvT3[i] = CalcAuxModInvT3[i+1];
}
CalcAuxModInvT3[i] = (CalcAuxModInvT3[i]<0? DosALa63: DosALa63-1);
NbrShifts = 0; Mask = 1;
}
} while (((CalcAuxModInvT3[0]^DosALa63) & Mask) == 0); /* end while */
if (NbrShifts != 0) {
for (i=0; i<NbrLength-1; i++) {
CalcAuxModInvT3[i] = ((CalcAuxModInvT3[i]^DosALa63) >>> NbrShifts |
CalcAuxModInvT3[i+1] << (64-NbrShifts)) ^ DosALa63;
}
CalcAuxModInvT3[i] = ((CalcAuxModInvT3[i]^DosALa63) >> NbrShifts) ^
DosALa63;
}
} /* end if */
Pass = 1;
// Step Y5. If t3 is positive, set u1 <- t1, u3 <- t3
// else, set v1 <- v - t1, v3 <- -t3.
if (CalcAuxModInvT3[NbrLength - 1] < 0) {
for (i=0; i<NbrLength; i++) {
CalcAuxModInvU1[i] = CalcAuxModInvT1[i];
CalcAuxModInvU3[i] = CalcAuxModInvT3[i];
}
}
else {
Cy = DosALa63;
Cy1 = 0;
for (i=0; i<NbrLength; i++) {
CalcAuxModInvV1[i] = Result = Cy + CalcAuxModInvV[i] - CalcAuxModInvT1[i];
Cy = (Result > CalcAuxModInvV[i] || (Result == CalcAuxModInvV[i] && Cy != DosALa63)?DosALa63-1:DosALa63);
CalcAuxModInvV3[i] = Cy1 - CalcAuxModInvT3[i];
Cy1 = (Cy1 != 0 || CalcAuxModInvT3[i] != DosALa63? -1: 0);
}
}
// Step Y6. Set t1 <- u1 - v1, t3 <- u3 - v3.
Cy = Cy1 = DosALa63;
for (i=0; i<NbrLength; i++) {
CalcAuxModInvT1[i] = Result = Cy + CalcAuxModInvU1[i] - CalcAuxModInvV1[i];
Cy = (Result > CalcAuxModInvU1[i] || (Result == CalcAuxModInvU1[i] && Cy != DosALa63)? DosALa63-1:DosALa63);
CalcAuxModInvT3[i] = Result = Cy1 + CalcAuxModInvU3[i] - CalcAuxModInvV3[i];
Cy1 = (Result > CalcAuxModInvU3[i] || (Result == CalcAuxModInvU3[i] && Cy1 != DosALa63)? DosALa63-1:DosALa63);
}
// Step Y7. If t1<0, set t1 <- t1 + v.
if (CalcAuxModInvT1[NbrLength-1] >= 0) {
Cy=DosALa63;
for (i=0; i<NbrLength; i++) {
Result = Cy + CalcAuxModInvT1[i] + CalcAuxModInvV[i];
if (Cy == DosALa63) {
Cy = (Result < CalcAuxModInvT1[i] || Result < CalcAuxModInvV[i]?
DosALa63+1: DosALa63);
}
else {
Cy = (Result <= CalcAuxModInvT1[i] || Result <= CalcAuxModInvV[i]?
DosALa63+1: DosALa63);
}
CalcAuxModInvT1[i] = Result;
}
}
// Step Y8. If t3 is not zero, go back to step Y3.
for (i=0; i<NbrLength; i++) {
if (CalcAuxModInvT3[i] != DosALa63) {break;}
}
} while (i < NbrLength);
for (i=NumberLength/2-1; i>=0; i--) {
inv[2*i] = CalcAuxModInvU1[i] & DosALa32_1;
inv[2*i+1] = (CalcAuxModInvU1[i] + DosALa63) >>> 32;
}
if (NumberLength%2 == 1) {
inv[NumberLength-1] = CalcAuxModInvU1[NbrLength-1] & DosALa32_1;
}
}
private String BigNbrToString(long Nbr[]) {
long Rem;
int i;
boolean ChSign = false;
String nbrOutput="";
if (Nbr[NumberLength-1] >= DosALa31) {
ChSignBigNbr(Nbr);
ChSign = true;
}
System.arraycopy(Nbr,0,CalcBigNbr,0,NumberLength);
do {
Rem = 0;
for (i=NumberLength - 1; i>=0; i--) {
CalcBigNbr[i] += Rem << 32;
Rem = CalcBigNbr[i] % Mi;
CalcBigNbr[i] /= Mi;
}
nbrOutput = ((Rem+Mi)+"").substring(1) + nbrOutput;
for (i=0; i<NumberLength; i++) {
if (CalcBigNbr[i] != 0) {break;}
}
} while (i<NumberLength);
while (nbrOutput.charAt(0)=='0' && nbrOutput.length() > 1) {
nbrOutput = nbrOutput.substring(1);
}
if (ChSign) {
ChSignBigNbr(Nbr);
nbrOutput = "-"+nbrOutput;
}
return nbrOutput;
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -