I think there is an assumption that both parties are ordering their possible choices in an identical manner, but I am unsure.
So if I told you the product of two numbers (positive integers) was 3, you immediately know 3 is prime and therefore the numbers are 1,3. Therefore either they cannot say they don't know if they were told 3. We can go through every combination and find what possibilities they could be.
Well, it cannot be 1,1 or 1,2 or 1,3 because those produce products of 1, 2 and 3 because they don't have any other pair that can generate them. The same is true of 2,3 which is the only way to get six or 2,4 the only way to get 8. And 3,3 or 3,4 which are the only way to get 9 and 12. And lastly 4,4 is the only way to get to 16. You'll note that this is almost all pairs which is easy to iterate over by making the second number greater than or equal to the first. The only pairs left are 1,4 and 2,2 both of which produce a product of 4. So we, as the sun person, now know the product must be four. Given the product and the sum, we can deduce that it's 1,4 because we were told the sun was 5.
When it goes to 100, it's the same process. Except now I have to iteratively eliminate pairs until there is only one solution.
After understanding that idea, the rest is just tedious logic/brute-force-search, I believe.
It's also possible that there is ambiguity in the statement or something like that. Hard to say exactly what part isn't connecting with you.
I don't have any guarantees that both of them are sorting each list the same. So how does "I don't have enough information" relay which of those list items to eliminate?
When the person knowing the product says he doesn't know the answer, the sum person now checks the product list for all products with only 1 pair. These pairs can now be removed from the sum and product list. That actually culls the sum list and some entries that previously had 2 or more options now have 1 less. If the entry for the known sum has only 1 pair, he knows the answer. Otherwise he doesn't and now the culling continues with all sums that have only 1 pair. Repeat until you have the solution.
No ordering required. The algorithm can terminate at different rounds depending on the picked number and for some N (like 4) might not have a solution at all! For the given riddle the exact turn the solution was found is given through the conversation.
This is a pretty neat explanation https://alexanderell.is/posts/numbers-game/