I don't think you can get it in ONE lookup, but you don't have to go through all the keys either. For 31456 xxxx you just have to test 31, 314, 3145 and 31456:

#!/bin/perl -w
use strict;

my %hash = (31123 => 1,
         31456 => 2,
         32123 => 3,
         32456 => 4,
         33      => 5,
         3361  => 6,
         );

foreach my $number ( qw( 31456000001 33456000001))
  { my @digits= split //, $number, 6;
    my( $prefix, $value); 
    foreach my $prefix_length ( 1..4)
      { my $trying= join '', @digits[0..$prefix_length];
        if( exists $hash{$trying})
          { $value= $hash{$trying};
            $prefix= $trying;
          }
      }
    if( defined $value)
      { print "$number => $value ($prefix)\n"; }
    else
      { warn "no value found for $number\n"; }
  }
[download]