So one thing im thinking could work is to do a sort of probabilistic birhtday attack. Like you could do a binary search, where in every step you narrow down on the bucket with more data.
So like lets say a year had 256 days and you want to find colliding birthdays. First you would check how many birthdays in 0-127 vs 128-255. This takes just two counters - very little storage. Then lets say the former has more. You'd try 0-63 vs 64-127. Etc.
But yeah this will of course miss collisions. But I think if you have enough children (where enough is still pretty close to sqrt(n)) it should have a good chance of finding a collision.
And subdividing into many buckets at a time will miss less collisions, but require more storage - a tradeoff can be used.
So like lets say a year had 256 days and you want to find colliding birthdays. First you would check how many birthdays in 0-127 vs 128-255. This takes just two counters - very little storage. Then lets say the former has more. You'd try 0-63 vs 64-127. Etc.
But yeah this will of course miss collisions. But I think if you have enough children (where enough is still pretty close to sqrt(n)) it should have a good chance of finding a collision.
And subdividing into many buckets at a time will miss less collisions, but require more storage - a tradeoff can be used.