An interesting way to partition a number
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 2(r) - 1. We give a recurrence relation to enumerate all s-partitions of it 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(log n) and can be generated in O(log n) steps. A d-partition may have a potential application in cryptography as we demonstrate its use in a distributed algorithm to compute a(n) mod m, a key computation intensive step in many cryptographic algorithms. (C) 1999 Elsevier Science B.V. All rights reserved.
cryptographic algorithm integer partitions distributed computing