{"entities":{"Q1334636":{"pageid":1345375,"ns":120,"title":"Item:Q1334636","lastrevid":67586748,"modified":"2026-04-12T18:56:10Z","type":"item","id":"Q1334636","labels":{"en":{"language":"en","value":"Fast RNS division algorithms for fixed divisors with application to RSA encryption"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 643654"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$29D172DB-E5A4-4693-8F22-0566AA4FDAFC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f83be194adeb60e116f42262f22e16125eebe23d","datavalue":{"value":{"text":"Fast RNS division algorithms for fixed divisors with application to RSA encryption","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1334636$752FC037-4666-4426-959F-FA3494C55C78","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"faba014c67e564cd4914fe9b87242aa1ffbd9767","datavalue":{"value":"0813.94008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334636$AF7F58BA-0C30-443D-8FCE-7D14A571D1C8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b670c5983f448fdf4d69752f49817b5e84eaab22","datavalue":{"value":"10.1016/0020-0190(94)00099-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334636$473AA8DC-2301-4CE6-ACCA-9CAE65C347DD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$1F2A69BD-C576-4B65-86F7-B695545062B2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c8ed3bb629960f79b097c1d049886bd39178543","datavalue":{"value":{"time":"+1994-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1334636$85BBF503-A3E9-4503-8E5C-84F1D9EC50F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f03a01a22cb6a870226e6297f24305130f993a8b","datavalue":{"value":"Residue number systems (RNS) have received much attention for high- throughput computations due to its advantage of fast addition and multiplication over other number systems. This paper presents two algorithms for RNS division with fixed divisors that achieve \\(O(n)\\) time complexity for each division, where \\(n\\) is the number of moduli. The first algorithm uses the well-known division method of multiplying by the divisor reciprocal. The second algorithm, which is faster than the first one but requires more space, is based on the Chinese Remainder Theorem decoding and table lookup, and requires the divisor to be relative prime to all moduli. Adaptation of both algorithms for RSA encryption is also described. It is shown that the first and second algorithms respectively lead to \\(4n + b\\) and \\(2n\\) time steps per modular multiplication, where \\(b\\) is the number of bits in the largest modulus.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334636$8DAA8FA6-B6EA-4290-BA4E-073D8935BAB0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334636$792DF0CB-E765-46FA-84AB-CFBF1D687A5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334636$154827C5-22CA-401A-AE17-BDA3BD3D7641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334636$7460A835-E725-47CE-B66E-F290DFAB8164","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4a20f7576ce80b01b2af8851193893696576b3f1","datavalue":{"value":"643654","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334636$8B7736D9-D789-4627-A129-BEAB8B17D056","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c209d8d0ece36734d529e2a8272a6b2d21a903b","datavalue":{"value":"residue number systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334636$AA4E35E0-E78C-4BEC-BE8C-3E1B780EC2C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d54d97c9d74a7974164bd27bc3725f50a6bd71c8","datavalue":{"value":"cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334636$BA5E59AC-34DD-45E8-9586-B22395F51027","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35516fd73598e50c1d55d81030f66ffd72abcf6a","datavalue":{"value":"sign detection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334636$6FECE713-7320-4BC8-B0FA-66DE1BBCBE08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33c83d5142aaa8d798578ed711216fa831c5585","datavalue":{"value":"computer arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334636$74C6DF0C-FAAA-45DD-95CF-B25EBEA26759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334636$13CAE85D-7306-47E9-88BB-E56DD2E219CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11070bb7feb158ed3f99983ae8e1366e1c1c87fa","datavalue":{"value":"RSA encryption","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334636$E4729DF0-3F81-4948-A81C-8D4C83FE863A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5b7d825081d90817135f688e03582cc5c56d14c","datavalue":{"value":"modular multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334636$EA12899F-8866-48A3-B78D-A1E84C47F983","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7bb465a4e87da6d8a0585f4369938135ff9f40fa","datavalue":{"value":{"entity-type":"item","numeric-id":1205889,"id":"Q1205889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$89389E80-3320-4BE3-A331-96F08D64BB5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d05c096695151c9a36ef94b5932d4011ab8af373","datavalue":{"value":{"entity-type":"item","numeric-id":212519,"id":"Q212519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$66F667DE-DB22-4683-9EA7-AA56E826F109","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ee19f8e9c64fe4709a3938fc8706c769930f01ce","datavalue":{"value":{"entity-type":"item","numeric-id":182320,"id":"Q182320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$C23AE120-8FE9-457C-8B79-9C8B5BFDB47F","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$05673CB6-1EA3-42C3-A436-C04AFCD4FC48","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"05de7d1582d2fd78b753c33980321c06b1cddca4","datavalue":{"value":"https://doi.org/10.1016/0020-0190(94)00099-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1334636$0736B3C3-BEC0-4D1F-AE91-76F08E87A494","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"658c0f544409001fbeb5e50f7cc2fcb954aff947","datavalue":{"value":"W2103983091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334636$75931377-69F1-4B43-B5EF-7CF82DC3EB06","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0008993f8ae66d8445fbec091e9b31bd18fec533","datavalue":{"value":{"entity-type":"item","numeric-id":3325037,"id":"Q3325037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$2800E0BA-AC12-4CE9-BC02-F0F84D194E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56478555ee421c24834139cd689f5b7ac95c4207","datavalue":{"value":{"entity-type":"item","numeric-id":1263285,"id":"Q1263285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$E4DFD81E-9632-40FC-ABAF-41BE1F781D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5682d1b1e8a55148344addc3a59e346025562681","datavalue":{"value":{"entity-type":"item","numeric-id":5375310,"id":"Q5375310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$E168B22D-E72F-4A10-AF0E-FFCF1894973B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00951cbffe1efa969b725410072fdd42e6e96387","datavalue":{"value":{"entity-type":"item","numeric-id":1324323,"id":"Q1324323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$7C612DF3-4842-40B4-AF37-B85589A21BFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96d2b555c0e4e0f46c4272573fc15f8561d2e100","datavalue":{"value":{"entity-type":"item","numeric-id":1205890,"id":"Q1205890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$050D7B1D-1A39-4869-A19F-7B8C9A2D7505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e36bca0800ff220e011be4e5dd8f71a91946b832","datavalue":{"value":{"entity-type":"item","numeric-id":5375361,"id":"Q5375361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$A5652961-89EC-4F06-A0E4-D0F15B32E52E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a1a6a287d9243437b8a676a895453e0737ae618","datavalue":{"value":{"entity-type":"item","numeric-id":5553682,"id":"Q5553682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334636$029DE0D0-F1D5-4129-AB58-EB60AF2DB4BF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98e12824357165a2c34b47884a54b9f9e42a9779","datavalue":{"value":{"entity-type":"item","numeric-id":1263285,"id":"Q1263285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fed42fbebd793b3ba77f0b8ddbe66fb0a2d83a0","datavalue":{"value":{"amount":"+0.8021745681762695","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1334636$EAC93AA7-E8C0-49A2-B402-8452D3063B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff86fd6468fb6137d6b5c753d423be8aeae9437e","datavalue":{"value":{"entity-type":"item","numeric-id":1324323,"id":"Q1324323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07bf9f1594b1692539c3fdb7d955b39cf2516616","datavalue":{"value":{"amount":"+0.7750212550163269","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1334636$31A7C017-27A9-4845-9B48-7084257EB36B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14beb4e954ab2575c31e7c6deeb9c81166cb6ee3","datavalue":{"value":{"entity-type":"item","numeric-id":3154810,"id":"Q3154810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22a8133069f2d8947c30ab7fe4d5c4d136b6bb58","datavalue":{"value":{"amount":"+0.7721555829048157","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1334636$8198F3AD-B9FE-4629-A71F-27E9C0A6C69B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86313f72bb4c350e761564eb02f7d429725d91ea","datavalue":{"value":{"entity-type":"item","numeric-id":4421199,"id":"Q4421199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e63134aa350c5210c5d862a47288dc9637ec3bb","datavalue":{"value":{"amount":"+0.766453742980957","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1334636$E444F7FA-F5FC-4B7B-904B-2E572DF7A4FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57a08c1fa8a577e3fa98cc2261b03d3176183a22","datavalue":{"value":{"entity-type":"item","numeric-id":1919392,"id":"Q1919392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58c27144293de700853f123f40a67900377b5f9d","datavalue":{"value":{"amount":"+0.7661923170089722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1334636$3570B137-54ED-42F5-BDA9-421ED5B24EED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fast RNS division algorithms for fixed divisors with application to RSA encryption","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fast_RNS_division_algorithms_for_fixed_divisors_with_application_to_RSA_encryption"}}}}}