"Prime Rewards" Credit Card
 

I have a credit card with a 16-digit number, having the following properties:

1. The full 16-digit CC number is prime;
2. The rightmost 8-digit portion of the CC number is prime;
3. The rightmost 4-digit portion of the CC number is prime;
4. The CC number satisfies the standard [URL="http://en.wikipedia.org/wiki/Luhn_algorithm"]checksum[/URL].

How many possible 16-digit numbers fit the criteria?

(Note: My actual credit card number fits this description, so there is a possible financial-fraud incentive in play here.)

Without looking in to how the checksum affects it, and assuming log(5*10^[x-1]) is a good estimate for the chances of a x-digit number being prime, I estimate that 1 in 5458 credit card numbers satisfy the conditions. Given that there are about 10^15 combinations, (assuming all 1 million possible issuer IDs each have 1 billion accounts, and taking into account that the last digit is based on the previous 15...not likely now, but we're looking for any possible number, not just ones that are likely to occur today) I'd say roughly 183 billion possible numbers match your criteria. A great deal are eliminated, yes, but a great deal still remain, so your CC number is safe. I'm sure someone will come along with a more precise answer. :smile:
My estimates are rough, especially because I ignored the checkdigit, but I doubt it would have [I]so[/I] much of an effect that it turns 183 billion into 1, or even 20000. I'd guess that it tends to be practically random
I wonder how much information regarding primality and/or factoring you'd have to give to usually be able to uniquely identify a CC number. e.g. would "the full 16 digits is prime, the last 15 digits has 2 prime factors, the last 14 digits has 2 prime factors, etc." be sufficient?

[QUOTE=Mini-Geek;247546]I'd say roughly 183 billion possible numbers match your criteria.[/QUOTE]

I'd think more than that. If the 16-digit number is prime, then the last digit is relatively prime to 10*, so the odds improve by a factor of ~ (5/2)^2.

* 0000000000000002 and 0000000000000005 fail the Luhn test.

Man, I could see the headlines already...

"Mathematician becomes victim of fraud after posting credit card riddle online"

Ernst will be in trouble when his trash bins are raided (or mailbox snooped); the piece of evidence that will greatly narrow the search is the [SPOILER]name of the issuing bank[/SPOILER]. This determines the leftmost four digits (or a small set of these).

[SPOILER] If you ever asked yourself: 'why are all bomb recipes in movies are so bogus?' - that's because they know their liabilities. Here, anyone with material suggestions also sets h{im,er}self up for abetting the criminals.
[/SPOILER]

Improving the odds from one-in-a-trillion to one-in-a-billion...

Looks like much less than a billion if the first four digits are known; my shot is about (/10 is from parity test)
1766126 * 10^4/10 / l(10^15)
~= 51,134,585

[QUOTE=Batalov;247582]Looks like much less than a billion if the first four digits are known; my shot is about (/10 is from parity test)
1766126 * 10^4/10 / l(10^15)
~= 51,134,585[/QUOTE]

I get ~2x that if you can get all 4 digits. I assumed you'd get 3 out of 4 which seems more likely to me.

[QUOTE=Batalov;247568]the piece of evidence that will greatly narrow the search is the [SPOILER]name of the issuing bank[/SPOILER]. This determines the leftmost four digits (or a small set of these). [/QUOTE]

According to [URL="http://www.merriampark.com/anatomycc.htm"]the site[/URL] linked earlier regarding the checkdigit, it's not just 4, but the first 6 digits that are the issuer identifiers. If you also are able to find the person's last 4 digits of a credit card number (much easier to find on receipts, etc. than the full number), you now know 10 of 16 of the digits of credit card number, including the checkdigit. That still leaves 6 digits, or 1 million possible numbers. But if this is the same card that you know contains the 16, 8, and 4 digit primes, and you have that many of the digits, you would probably be able to infer the remaining digits, or at least narrow it to just a handful.

[QUOTE=Mini-Geek;247546] Given that there are about 10^15 combinations, [/QUOTE]

Don't go to work in a bank! There are exactly 10^15 valid card combinations. (Fix all numbers, except the first, then there is only one possibility for the first digit to make it a valid card number that satisfy Luhn algorithm).

If we "forget" that the card is prime, but other 3 requirements are true, then it is easy to calculate this number:
[code]
s=0;forprime(p=2,10^8,s+=isprime(p%10000));return(s*10^7)
17673550000000
[/code]
This suggests for the true problem s/log(10^16)*2*5/4=1.2*10^12 value.
By simple simulations running 10^6 random card numbers gives: 128, 112, 121, 148 valid card numbers, so it gives also about 120*10^10=1.2*10^12 approximation.

Even when given the first 6 digits and last 4 digits (6 digits unknown) of an example credit card number I just tried, and given the 4 requirements in the first post, in the example I tried, 1,057 out of 1,000,000 numbers still remained. With the first 6 and last 5 (5 digits unknown), 119 out of 100,000 remained. These results approximately agree with R. Gerbicz's estimate: a little more than 1 out of 1,000 numbers remains after applying all those criteria. So to have a very good chance of calculating a credit card number based on the criteria, you can only be missing 3 of the digits. If you could try 6 wrong numbers (on average) without worrying, missing 4 of the digits would be ok, but that's still like having the financial institution and the last 6 of the card number, and they never reveal that much info.