BITS AND RELATIVE ORDER FROM RESIDUES, SPACE EFFICIENTLY

被引：17

作者：

DIETZ, PF ^{[1
]}

MACARIE, II ^{[1
]}

SEIFERAS, JI ^{[1
]}

机构：

[1] UNIV ROCHESTER,DEPT COMP SCI,ROCHESTER,NY 14627

来源：

INFORMATION PROCESSING LETTERS | 1994年 / 50卷 / 03期

关键词：

COMPUTATIONAL COMPLEXITY; RESIDUE NUMBER SYSTEM; CHINESE REMAINDER THEOREM; BINARY REPRESENTATION; SIGN DETECTION; PARITY DETECTION; SPACE COMPLEXITY;

D O I：

10.1016/0020-0190(94)00021-2

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

For each k, let P(k) be the product of the first k primes. Each integer in the interval [0, P(k)) is determined by its residues modulo these k primes. We address the problems of space-efficiently computing the bits and the relative order of such numbers from their residues.

引用

页码：123 / 127

页数：5

共 18 条

[1] RELATING TIME AND SPACE TO SIZE AND DEPTH [J].

BORODIN, A .

SIAM JOURNAL ON COMPUTING, 1977, 6 (04) :733-744

[2]

CHOR B, 1986, 2 ISSUES PUBLIC KEY

[3] FAST PARALLEL ARITHMETIC VIA MODULAR REPRESENTATION [J].

DAVIDA, GI ;

LITOW, B .

SIAM JOURNAL ON COMPUTING, 1991, 20 (04) :756-765

[4]

Garner H. L., 1959, IRE T ELECTRON COMPU, V8, P140, DOI DOI 10.1109/TEC.1959.5219515

[5]

JUNG H, 1984, LECT NOTES COMPUT SC, V172, P281

[6]

Keir Y. A., 1962, IRE T ELECTRON COM, V11, P501

[7] A NOVEL DIVISION ALGORITHM FOR THE RESIDUE NUMBER SYSTEM [J].

LU, M ;

CHIANG, JS .

IEEE TRANSACTIONS ON COMPUTERS, 1992, 41 (08) :1026-1032

[8]

MACARIE II, 1994, 11TH P ANN S THEOR A, V775, P109

[9]

MILLER DD, 1983, 26TH P MIDW S CIRC S, P389

[10] LOGARITHMIC DEPTH CIRCUITS FOR ALGEBRAIC-FUNCTIONS [J].

REIF, JH .

SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :231-242

← 1 2 →