An interesting way to partition a number
| Autor: | Manfred Kuechler |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Discrete mathematics
Recurrence relation Computational complexity theory business.industry Cryptography Natural number Lexicographical order Upper and lower bounds Computer Science Applications Theoretical Computer Science Combinatorics Distributed algorithm Signal Processing Partition (number theory) business Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 71:141-148 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/s0020-0190(99)00090-3 |
| Popis: | This note reports an interesting kind of partition, called an s-partition, for a natural number n. Each cell in an s-partition has an element of the form 2r−1. We give a recurrence relation to enumerate all s-partitions of n and also derive an upper bound on the number of possible s-partitions. We define a relation of domination to get a lexical order on s-partitions and show that a unique partition, called d-partition, dominates all other s-partitions of n. A d-partition has the smallest cardinality of O(logn) and can be generated in O(logn) steps. A d-partition may have a potential application in cryptography as we demonstrate its use in a distributed algorithm to compute an mod m, a key computation intensive step in many cryptographic algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect